waashk/acm huggingface dataset:
apl87  i first began developing a formal language for use in teaching in the graduate program in automatic data processing established by professor howard aiken at harvard in 1955\. this language, now known as apl, has since passed through several phases, the main ones being documented in three publications [1-3]; my book a programming language in 1962, the apl\360 manual in 1968, and the aplsv manual in 1975. the last two were co-authored with a.d. falkoff.  the specifications of the language provided by these publications were later supplemented by more philosophical studies that discussed the design principles followed, and the major design choices made. these include the design of apl [4], and the evolution of apl [5], by me and falkoff, and the story of o, by e.e. mcdonnell [6].  because of implementations produced by various manufacturers, and because of attempts to inject aspects of other languages (as in aplgol), many diverse lines of development have been pursued. these have been largely reported in manuals, in the proceedings of apl conferences, and in journals such as apl quote-quad (association for computing machinery), and vector (british computing society).  in 1978 i began a line of development which has been reported largely in documents internal to ibm corp. [7] and to i.p. sharp associates [8-10], but also in apl conferences [11-13]. this work has culminated in a dictionary of apl, scheduled to appear in an early issue of apl quote-quad [14]; in what follows it will be referred to as "the dictionary".  the present paper is a companion study in the manner of [4-6]. a preview of it was presented in november of last year at an internal ibm conference that commemorated the 20th anniversary of the initiation of the apl timesharing service within ibm.  the major points to be discussed here include terminology, the apl alphabet, word formation, parsing rules, mixed functions, operators, and localization. in discussing decisions made in the early days by me and colleagues in the apl group in the t.j. watson research center, (notably a.d. falkoff and l.m. breed), i will use the term we; this usage is not meant to imply their agreement with the current thinking of myself and present colleagues at i.p. sharp associates as presented in the dictionary.  although there is no current implementation of the entire dictionary, several implementations embody significant parts of it, such as the application of operators to derived and user-defined functions, and the production of "mixed" arrays by expressions such as 3 4 5, 'abcd'. two implementations [13, 15] are particularly close to the dictionary; the latter was used in all executed examples in this paper.  kenneth e. iverson
efficient computation of interprocedural definition-use chains  the dependencies that exist among definitions and uses of variables in a program are required by many language-processing tools. this paper considers the computation of definition-use and use-definition chains that extend across procedure boundaries at call and return sites. intraprocedural definition and use information is abstracted for each procedure and is used to construct an interprocedural flow graph. this intraprocedural data-flow information is then propagated throughout the program via the interprocedural flow graph to obtain sets of reaching definitions and/or reachable uses for reach interprocedural control point, including procedure entry, exit, call, and return. interprocedural definition-use and/or use-definition chains are computed from this reaching information. the technique handles the interprocedural effects of the data flow caused by both reference parameters and global variables, while preserving the calling context of called procedures. additionally, recursion, aliasing, and separate compilation are handled. the technique has been implemented using a sun-4 workstation and incorporated into an interprocedural data-flow tester. results from experiments indicate the practicality of the technique, both in terms of the size of the interprocedural flow graph and the size of the data-flow sets.  mary jean harrold mary lou soffa
a very fast algorithm for ram compression compressed virtual memory systems have been suggested, and in some cases implemented, to improve the effectiveness of use of physical ram. however, most proposals and/or implementations are based on adaptive compression algorithms which achieve good compression ratios, but are slow compared to a local disk. hence, they can only give some advantage with very slow (e.g. network-mounted) swap devices. in this paper we show that in many cases memory pages contain highly compressible data, with a very large amount of zero-valued elements. this suggests the replacement of slow, adaptive compression algorithms with very fast ones based on static huffman codes.we present one such algorithm which, paired with a careful layout of the data, is able to compress 4kb pages at 40mb/s even when implemented in software on an inexpensive pentium 100 system. we also show that the algorithm can achieve interesting compression ratios despite its simplicity.since the compression/decompression speed of our algorithms exceeds disk bandwidth, its use in a compressed vm system can lead to both memory savings and speed improvements in servicing page faults. in this paper we discuss some possible applications of the algorithm in a compressed vm system. luigi rizzo
compositional pointer and escape analysis for java programs  this paper presents a combined pointer and escape analysis algorithm for java programs. the algorithm is based on the abstraction of points-to escape graphs, which characterize how local variables and fields in objects refer to other objects. each points-to escape graph also contains escape information, which characterizes how objects allocated in one region of the program can escape to be accessed by another region. the algorithm is designed to analyze arbitrary regions of complete or incomplete programs, obtaining complete information for objects that do not escape the analyzed regions.  we have developed an implementation that uses the escape information to eliminate synchronization for objects that are accessed by only one thread and to allocate objects on the stack instead of in the heap. our experimental results are encouraging. we were able to analyze programs tens of thousands of lines long. for our benchmark programs, our algorithms enable the elimination of between 24% and 67% of the synchronization operations. they also enable the stack allocation of between 22% and 95% of the objects.  john whaley martin rinard
checking safety properties using compositional reachability analysis  the software architecture of a distributed program can be represented by a hierarchical composition of subsystems, with interacting processes at the leaves of the hierarchy. compositional reachability analysis (cra) is a promising state reduction technique which can be automated and used in stages to derive the overall behavior of a distributed program based on its architecture. cra is particularly suitable for the analysis of programs that are subject to evolutionary change. when a program evolves, only the behaviors of those subsystems affected by the change need be reevaluated. the technique however has a limitation. the properties available for analysis are constrained by the set of actions that remain globally observable. properties involving actions encapsulated by subsystems may therefore not be analyzed. in this article, we enhance the cra technique to check safety properties which may contain actions that are not globally observable. to achieve this, the state machine model is augmented with a special trap state labeled as π. we propose a scheme to transform, in stages, a property that involves hidden actions to one that involves only globally observable actions. the enhanced technique also includes a mechanism aiming at reducing the debugging effort. the technique is illustrated using a gas station system example.  shing chi cheung jeff kramer
data flow equations for explicitly parallel programs  we present a solution to the reaching definitions problem for programs with explicit lexically specified parallel constructs, such as cobegin/coend or parallel_sections, both with and without explicit synchronization operations, such as post, wait or advance. the reaching definitions information for sequential programs is used to solve many standard optimization problems. in parallel programs, this information can also be used to explicitly direct communication and data ownership. although work has been done on analyzing parallel programs to detect data races, little work has been done on optimizing such programs.  we show how the memory consistency model specified by an explicitly parallel programming language can influence the complexity of the reaching definitions problem. by selecting the "weakest" memory consistency semantics, we can efficiently solve the reaching definitions problem for correct programs.  dirk grunwald harini srinivasan
an automated fortran documenter  we have written a set of programs designed to help r and d programmers document their fortran programs more effectively. the central program reads fortran source code and asks the programmer questions about things it has not heard of before. it inserts the answers to these questions as comments into the fortran code. the comments, as well as extensive cross-reference information, are also written to an unformatted file. other programs read this file to produce printed information or to act as an interactive document.  timothy e. erickson
integrating message-passing and shared-memory: early experience  this paper discusses some of the issues involved in implementing a shared- address space programming model on large-scale, distributed-memory multiprocessors. while such a programming model can be implemented on both shared-memory and message-passing architectures, we argue that the transparent, coherent caching of global data provided by many shared-memory architectures is of crucial importance. because message-passing mechanisms ar much more efficient than shared-memory loads and stores for certain types of interprocessor communication and synchronization operations, hwoever, we argue for building multiprocessors that efficiently support both shared-memory and message- passing mechnisms. we describe an architecture, alewife, that integrates support for shared-memory and message-passing through a simple interface; we expect the compiler and runtime system to cooperate in using appropriate hardware mechanisms that are most efficient for specific operations. we report on both integrated and exclusively shared-memory implementations of our runtime system and two applications. the integrated runtime system drastically cuts down the cost of communication incurred by the scheduling, load balancing, and certain synchronization operations. we also present preliminary performance results comparing the two systems.  david kranz kirk johnson anant agarwal john kubiatowicz beng-hong lim
the response of job classes with distinct policy functions(extended abstract)  policy function schedulers provide a flexible framework for implementing a wide range of different scheduling schemes. in such schedulers, the priority of a job at any instant in time is defined by the difference between the time it spent in the system and an arbitrary function of its attained service time. the latter is called the policy function and acts as the functional parameter that specifies a particular scheduling scheme. for instance, a constant policy function specifies the first-come, first-serve scheduling scheme. by changing the policy function, the system behavior can be adjusted to better conform with desired response characteristics. it is common to express response characteristics in terms of a response function, the average response time of a job conditioned on its service requirement in equilibrium.  in this paper, we analyze processor-sharing m/g/1 systems in which the priorities of different classes of jobs are determined by distinct policy functions.  manfred ruschitzka
simple and effective link-time optimization of modula-3 programs  modula-3 supports development of modular programs by separating an object's interface from its implementation. this separation induces a runtime overhead in the implementation of objects, because it prevents the compiler from having complete information about a program's type hierarchy. this overhead can be reduced at link time, when the entire type hierarchy becomes available. we describe opportunities for link-time optimization of modula-3, present two link-time optimizations that reduce the runtime costs of modula-3's opaque types and methods, and show how link-time optimization could provide c++ which the benefits of opaques types at no additional runtime cost.  our optimization techniques are implemented in mld, a retargetable linker for the mips, sparc, and intel 486, mld links a machine- independent intermediate code that is suitable for link-time optimization and code generation. linking intermediate code simplifies implementation of the optimizations and makes it possible to evaluate them on a wide range of architectures. mld's optimizations are effective: they reduce the total number of instructions executed by up to 14% and convert as many as 79% of indirect calls to direct calls.  mary f. fernández
managed file distribution on the universe network  the file distribution system on the universe network consists of a distributed set of co-operating agents which provide clients with a reliable bulk file collection, transfer and delivery service. the agent systems incorporate specialised techniques for optimizing use of the satellite channel, as well as making available facilities for broadcast file distribution. the distributed system architecture and protocols are described, with emphasis on the separation of control and data transfer. a detailed presentation is given of the way in which agents interact with both hosts and other agents to achieve both reliability and robustness in the face of breaks in host or network availability. a description is given of the special transfer methods used and some of the possible applications for such a system. an indication is given of possible future developments to enable evolution from an experimental to service system.  christopher s cooper
optimistic active messages: a mechanism for scheduling communication with computation  low-overhead message passing is critical to the performance of many applications. active messages reduce the software overhead for message handling: messages are run as handlers instead of as threads, which avoids the overhead of thread management and the unnecessary data copying of other communication models. scheduling the execution of active messages is typically done by disabling and enabling interrupts, or by polling the network. this primitive scheduling control, combined with the fact that handlers are not schedulable entities, puts severe restrictions on the code that can be run in a message handler. this paper describes a new software mechanism, optimistic active messages (oam), that eliminates these restrictions; oams allow arbitrary user code to execute in handlers, and also allow handlers to block. despite this gain in expressiveness, oams perform as well as active messages.  we used oam as the base for an rpc system, optimistic rpc (orpc), for the thinking machines cm-5 multiprocessor; it consists of an optimized thread package and a stub compiler that hides communication details from the programmer. orpc is 1.5 to 5 times faster than traditional rpc (trpc) for small messages and performs as well as active messages (am). applications that primarily communicate using large data transfers or are fairly coarse-grained perform equally well, independent of whether ams, orpcs, or trpcs are used. for applications that send many short messages, however, the orpc and am implementations are up to three times faster than the trpc implementations. using orpc, programmers obtain the benefits of well-proven programming abstractions such as threads, mutexes, and condition variables, do not have to be concerned with communication details, and yet obtain nearly the performance of hand-coded active message programs.  deborah a. wallach wilson c. hsieh kirk l. johnson m. frans kaashoek william e. weihl
using properties for uniform interaction in the presto document system  most document or information management systems rely on hierarchies to organise documents (e.g. files, email messages or web bookmarks). however, the rigid structures of hierarchical schemes do not mesh well with the more fluid nature of everyday document practices. this paper describes presto, a prototype system that allows users to organise their documents entirely in terms of the properties those documents hold for users. properties provide a uniform mechanism for managing, coding, searching, retrieving and interacting with documents. we concentrate in particular on the challenges that property- based approaches present and the architecture we have developed to tackle them.  paul dourish w. keith edwards anthony lamarca michael salisbury
on parallel object oriented programming in fortran 90 the c++ programming language [6, 10] is well-known for its support of object oriented concepts, useful in abstraction modeling. containing many important features, its popularity is growing with a new generation of scientists anxious to bring clarity and flexibility to their programming efforts. nevertheless, most of the scientific applications in development and use today are based on fortran, the most popular language for scientific programming.fortran is not a static language, it has continually evolved to include the most recent proven ideas and concepts garnered from other programming languages. until recently, many of the most modern features were not available, complicating abstraction modeling for large scale development projects. this can make software difficult to comprehend, unsafe and potentially useless. the emergence of fortran 90 [3] has dramatically changed the prospects of fortran programming. not only are many of the most modern aspects of programming language techniques included in the standard, there are also specific new additions that will undoubtedly affect the next generation of all languages used in scientific programming [8]. charles d. norton viktor k. decyk boleslaw k. szymanski
customization and composition of distributed objects: middleware abstractions for policy management current middleware solutions such as corba and java's rmi emphasize compositional design by separating functional aspects of a system (_e.g._ objects) from the mechanisms used for interaction (_e.g._ remote procedure call through stubs and skeletons). while this is an effective solution for handling distributed interactions, higher-level requirements such as heterogeneity, availability, and adaptability require policies for resource management as well as interaction. we describe the _distributed connection language_ (dcl): an architecture description language based on the actor model of distributed objects. system components and the policies which govern an architecture are specified as encapsulated groups of actors. composition operators are used to build connections between components as well as customize their behavior. this customization is realized using a meta- architecture. we describe the syntax and semantics of dcl, and illustrate the language by way of several examples. mark astley gul a. agha
cost profile of a highly assured, secure operating system  the logical coprocessing kernel (lock) began as a research project to stretch the state of the art in secure computing by trying to meet or even exceed the "a1" requirements of the trusted computer system evaluation criteria (tcsec). over the span os seven years, the project was transformed into an effort to develop and deploy a product: the standard mail guard (smg). since the project took place under a us government contract, the development team needed to maintain detailed records of the time spent on the project. the records from 1987 to 1992 have been combined with information about software code size and error detection. this information has been used to examine the practical impacts of high assurance techniques on a large-scale software development program. tasks are associated with the a1 formal assurance requirements added approximately 58% to the development cost of security-critical software. in exchange for these costs, the formal assurance tasks (formal specifications, proofs, and specification code correspondence) uncovered 68% of the security flaws detected in lock's critical security mechanisms. however, a study of flaw detection during the smg program found that only 14% of all flaws detected were of the type that could be detected using formal assurance, and that the work of the formal assusrance team only accounted for 19% of all flaws detected. while formal assurance is clearly effective at detecting flaws, its practicality hinges on the degree to which the formally modeled system properties represent all of a system's esential properties.  richard e. smith
evolution of object behavior using context relations a collection of design patterns was described by gamma, helm, johnson, and vlissides in 1994. recognizing that designs change, each pattern ensures that a certain system aspect can vary over time such as the operations that can be applied to an object or the algorithm of a method. the patterns are described by constructs such as the inheritance and reference relations, attempting to emulate more dynamic relationships. as a result, the design patterns demonstrate how awkward it is to program natural concepts of behavioral evolution when using a traditional object-oriented language.in this paper we present a new relation between classes: the context relation. it directly supports behavioral evolution, and it is meaningful at the analysis, design, and implementation level. at the design level we picture a context relation as a new form of arrow between classes. at the implementation level we use a small extension of c++. the basic idea is that if class c is context-related to a base class b, then b-objects can get their functionality dynamically altered by c-objects. our language construct for doing this is a generalization of the method update in abadi and cardelli's imperative object calculus. a c-object may be explicitly attached to a b-object, or it may be implicitly attached to a group of b-objects for the duration of a method invocation. we demonstrate how the context relation can be used to easily model and program the adapter, bridge, chain of responsibility, decorator, iterator, observer, state, strategy, and visitor patterns. linda m. seiter jens palsberg karl j. lieberherr
an ada tmcompatible specification language  this paper describes a notation for the formal specification of software packages. the main influences are the guarded commands of dijkstra and the algebraic semantics of guttag. however, a novel operator denoted by % is introduced, which allows algorithms to be abstracted in a specification, thereby creating a true specification language rather than another higher level language. the notation, called adl/1, is designed to be used in conjunction with ada;tm but is equally suitable for other languages, and has been used for real time software written in assembler and in a pascal-like language.  n. c.l. beale peyton s.l. jones