waashk/acm huggingface dataset:
a formal description of the unix operating system  in this paper we discuss our approach to a formal description of the unix operating system [rit78a] [rit78b] [tho78], using milner's calculus of communicating systems (ccs) [mil80].  the paper focuses on the problems one encounters and the decisions one has to make when describing a system such as unix. we believe that the problems that arise in defining such a system are much less well understood than those, for example, related to the formalization of programming languages. in particular, this work is intended to serve several different purposes. one is an extensive test of the capabilities of ccs. we are applying ccs to the description of a moderately large system. this exercise has uncovered many shortcomings of the formalism; some of these we have overcome, while others are the subject of continuing research. for example, an important and difficult problem is the lack of any direct means of communicating ports as values.  thomas w. doeppner alessandro glacalone
re-targetability in software tools software tool construction is a risky business, with uncertain rewards. many tools never get used. this is a truism: software tools, however brilliantly conceived, well-designed, and meticulously constructed, have little impact unless they are actually adopted by real programmers. while there are no sure-fire ways of ensuring that a tool will be used, experience indicates that _retargetability_ is an important enabler for wide adoption. in this paper, we elaborate on the need for retargetability in software tools, describe some mechanisms that have proven useful in our experience, and outline our future research in the broader area of inter- operability and retargetability. premkumar t. devanbu
towards partially evaluating reflection in java  reflection plays a major role in the programming of generic applications. however, it introduces an interpretation layer which is detrimental to performance. a solution consists of relying on partial evaluation to remove this interpretation layer. this paper deals with improving a standard partial evaluator in order to handle the java reflection api. the improvements basically consist of taking type information into account when distinguishing between static and dynamic data, as well as introducing two new specialization actions: _reflection actions_. benchmarks using the serialization framework show the benefits of the approach.  mathias braux jacques noye
an ada package for dimensional analysis  this paper illustrates the use of ada's abstraction facilities---notably, operator overloading and type parameterization---to define an oft-requested feature: a way to attribute units of measure to variables and values. the definition given allows the programmer to specify units of measure for variables, constants, and parameters; checks uses of these entities for dimensional consistency; allows arithmetic between them, where legal; and provides scale conversions between commensurate units. it is not constrained to a particular system of measurement (such as the metric or english systems). although the definition is in standard ada and requires nothing special of the compiler, certain reasonable design choices in the compiler, discussed here at some length, can make its implementation particularly efficient.  paul n. hilfinger
on the correctness of semantic-syntax-directed translations  the correctness of semantic-syntax-directed translators (ssdts) is examined. ssdts are a generalization of syntax-directed translators in which semantic information is employed to partially direct the translator. sufficient conditions for an ssdt to be "semantic-preserving," or "correct," are presented. a further result shows that unless certain conditions are met, it is undecidable, in general, whether an ssdt is semantic-preserving.  ramachandran krishnaswamy arthur b. pyster
customization: optimizing compiler technology for self, a dynamically-typed object-oriented programming language  dynamically-typed object- oriented languages please programmers, but their lack of static type information penalizes performance. our new implementation techniques extract static type information from declaration-free programs. our system compiles several copies of a given procedure, each customized for one receiver type, so that the type of the receiver is bound at compile time. the compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. it splits calls, compiling a copy on each control path, optimized to the specific types on that path. coupling these new techniques with compile-time message lookup, aggressive procedure inlining, and traditional optimizations has doubled the performance of dynamically-typed object-oriented languages.  c. chambers d. ungar
developing a stage lighting system from scratch lula is a system for computer- assisted stage lighting design and control. whereas other systems for the same purpose are usually the results of long chains of incremental improvements of historic concepts, lula represents a complete redesign. whereas other systems focus on control aspects of lighting, lula focuses on design and generates control information from it. this approach gives significantly more flexibility to the lighting designer and shortens the design process itself. lula's design and implementation draw from a number of disciplines in advanced programming. it is written in scheme and runs atop plt scheme, and benefits from its high-level gui library. lula uses an algebraic model for lighting looks based on just three combinators. it employs functional reactive programming for all dynamic aspects of lighting, and is programmable via a functional reactive domain-specific language. lula is an actual product and has users who have neither interest in nor knowledge of functional programming. michael sperber
forward computation of dynamic program slices  a dynamic program slice is an executable part of the program whose behavior is identical, for the same program input, to that of the original program with respect to a variable(s) of interest at some execution position. it has been shown that dynamic slicing is useful for the purpose of debugging, testing and software maintenance. the existing methods of dynamic slice computation are based on "backward" analysis, i.e., after the execution trace of the program is first recorded, the dynamic slice algorithm traces backwards the execution trace to derive dynamic dependence relations that are then used to compute dynamic slices. for many programs, during their execution extremely high volume of information may be recorded that may prevent accurate dynamic slice computation. in this paper we present a novel approach of dynamic slice computation, referred to as forward approach of dynamic slice computation. in this method, dynamic slices are computed during program execution without major recording of the execution trace. the major advantage of the forward approach is that space complexity is bounded as opposed to the backward methods of slice computation.  bogdan korel satish yalamanchili
compiler-directed page coloring for multiprocessors this paper presents a new technique, _compiler-directed page coloring,_ that eliminates conflict misses in multiprocessor applications. it enables applications to make better use of the increased aggregate cache size available in a multiprocessor. this technique uses the compiler's knowledge of the access patterns of the parallelized applications to direct the operating system's virtual memory page mapping strategy. we demonstrate that this technique can lead to significant performance improvements over two commonly used page mapping strategies for machines with either direct-mapped or two-way set- associative caches. we also show that it is complementary to latency-hiding techniques such as prefetching.we implemented compiler-directed page coloring in the suif parallelizing compiler and on two commercial operating systems. we applied the technique to the spec95fp benchmark suite, a representative set of numeric programs. we used the simos machine simulator to analyze the applications and isolate their performance bottlenecks. we also validated these results on a real machine, an eight-processor 350mhz digital alphaserver. compiler-directed page coloring leads to significant performance improvements for several applications. overall, our technique improves the spec95fp rating for eight processors by 8% over digital unix's page mapping policy and by 20% over a page coloring, a standard page mapping policy. the suif compiler achieves a spec95fp ratio of 57.4, the highest ratio to date. edouard bugnion jennifer m. anderson todd c. mowry mendel rosenblum monica s. lam
compile time syntax analysis of apl programs  we present a technique for the compile-time determination of the syntactic attribute of names essential for the development of a compile-time parser for apl. the method is applicable to a large class of apl programs namely, programs which do not utilize certain features of the language allowing dynamic changes in the syntactic meaning of program statements. empirical evidence supports the hypothesis that the restricted apl language encompasses almost all existing apl code.  zvi weiss harry j. saal
a library of generic algorithms in ada  it is well-known that data abstractions are crucial to good software engineering practice. we argue that algorithmic abstractions, or generic algorithms, are perhaps even more important for software reusability. generic algorithms are parameterized procedural schemata that are completely independent of the underlying data representation and are derived from concrete, efficient algorithms. we discuss this notion with illustrations from the structure of an ada library of reusable software components we are presently developing.  david r. musser alexander a. stepanov
a portable user interface for a scientific programming environment  the subject of integrated programming environments for scientific computing has become very popular over the last few years. environments such as rn [cchk87] are being constructed to help coordinate the disjoint activities of editing, debugging, and performance tuning typically seen in the program development cycle. one key aspect of an integrated development setting is the library of user interface tools which are available to the environment builders. projects such as andrew [msch86] have begun to construct reusable user interface libraries for client applications. this paper describes the interface tool kit for the faust project being conducted at the university of illinois. faust is targeted at building a coherent development environment for scientific applications through the use of a library of portable user interface utilities.  vincent a. guarna yogesh gaur
external representations of objects of user-defined type  the portable programming language (ppl) is one of a number of recently designed programming languages that enable the user to define new types by giving their representations and operations in terms of those of previously available types. such provisions for the construction of objects of user- defined type have been discussed elsewhere; this work concerns the related problem of the external representations of such objects, both on input-output media and as written constants within the program text. we introduce an enhancement to the ppl design allowing specification of the external representations of objects of user-defined type. this extension to the ppl design means that objects of user-defined type can be read, written, and used as constants exactly as if their representations had been selected by the writer of the ppl compiler. the implementation and use of the added facilities are also discussed.  peter l. wallis
motivation for and current work on copaging cache (abstract only)  tools currently employed to aid in fully utilizing the processor capability of computer systems burdened with inherently slower memories include the use of virtual memory, instruction prefetching, and the implementation of cache memories as highspeed buffers between the cpu and primary memory. copaging cache is a cache which allows the overlapping of cache page-in or page-out operations with instruction execution(1). the motivation for a copaging cache comes partly from the successes and shortcomings of the 3 tools mentioned above. the presentation will be concerned with these motivating factors and briefly survey current research in the design of a viable copaging cache architecture.  linda turpin
eros: a fast capability system eros is a capability-based operating system for commodity processors which uses a single level storage model. the single level store's persistence is transparent to applications. the performance consequences of support for transparent persistence and capability-based architectures are generally believed to be negative. surprisingly, the basic operations of eros (such as ipc) are generally comparable in cost to similar operations in conventional systems. this is demonstrated with a set of microbenchmark measurements of semantically similar operations in linux.the eros system achieves its performance by coupling well-chosen abstract objects with caching techniques for those objects. the objects (processes, nodes, and pages) are well-supported by conventional hardware, reducing the overhead of capabilities. software-managed caching techniques for these objects reduce the cost of persistence. the resulting performance suggests that composing protected subsystems may be less costly than commonly believed. jonathan s. shapiro jonathan m. smith david j. farber
the performance of an object-oriented threads package  presto is an object-oriented threads package for writing parallel programs on a shared- memory multiprocessor. the system adds thread objects and synchronization objects to c++ to allow programmers to create and control parallelism. presto's object-oriented structure, along with its user-level thread implementation, simplifies customization of thread management primitives to meet application-specific needs.  the performance of thread primitives is crucial for parallel programs with fine-grained structure; therefore, the principal objective of this effort was to substantially improve presto's performance under heavy loads without sacrificing the benefits of its object-oriented interface. we discuss design and implementation issues for shared-memory multiprocessors, and the performance impact of various designs is shown through measurements on a 20-processor sequent symmetry multiprocessor.  john e. faust henry m. levy
omen: a strategy for testing object-oriented software  this paper presents a strategy for structural testing of object-oriented software systems with possibly unknown clients and unknown information about invoked methods. by exploiting the combined points-to and escape analysis developed for compiler optimization, our testing paradigm does not require a whole program representation to be in memory simultaneously for testing analysis. potential effects from outside the component under test are easily identified and reported to the tester. as client and server methods become known, the graph representation of object relationships is easily extended, allowing the computation of test tuples to be performed in a demand-driven manner, without requiring unnecessary computation of test tuples based on predictions of potential clients.  amie l. souter lori l. pollock
configuring stand-alone smalltalk-80 applications  the smalltalk-80 programming environment, though powerful for prototyping applications, does not have any mechanisms for constructing a stand-alone version of an application. traditionally, the application is bundled with an image including the entire development environment. production applications frequently require that the only interface visible to the end user be that of the application. a common misperception among smalltalk-80 application developers is that it is impossible to:  develop and deliver applications containing proprietary algorithms,  prevent inspection and modification of the application,  separate the development environment from the delivered application,  provide annotation of the application classes and methods without actually revealing the source code to the end user.  in this paper, we introduce various techniques and mechanisms for meeting these requirements.  s. sridhar
unidraw: a framework for building domain-specific  unidraw is a framework for creating object-oriented graphical editors in domains such as technical and artistic drawing, music composition, and cad. the unidraw architecture simplifies the construction of these editors by providing programming abstractions that are common across domains. unidraw defines four basic abstractions: components encapsulate the appearance and behavior of objects, tools support direct manipulation of components, commands define operations on components, and external representations define the mapping between components and a file or database. unidraw also supports multiple views, graphical connectivity, and dataflow between components. this paper presents unidraw and three prototype domain-specific editors we have developed with it: a schematic capture system, a user interface builder, and a drawing editor. experience indicates a substantial reduction in implementation time and effort compared with existing tools.  j. m. vlissides m. a. linton
an efficient approach to computing fixpoints for complex program analysis  a chief source of inefficiency in program analysis using abstract interpretation comes from the fact that a large context (i.e., problem state) is propagated from node to node during the course of an analysis. this problem can be addressed and largely alleviated by a technique we call context projection, which projects an input context for a node to the portion that is actually relevant and determines whether the node should be reevaluated based on the projected context. this technique reduces the cost of an evaluation and eliminates unnecessary evaluations. therefore, the efficiency of computing fixpoints over general lattices is greatly improved. a specific method, reachability, is presented as an example to accomplish context projection. experimental results using reachability show very convincing speedups (more than eight for larger programs) that demonstrate the practical significance of context projection.  li-ling chen williams ludwell harrison
attached processors in apl  an extension to the semantics of apl is proposed. it allows one apl processor (aplp) to attach another processor, which may be an (aplp) with its own workspace, or some other processor. a special case is signon from a terminal, where the attaching processor becomes a human user acting through a workstation. attached processors communicate through shared variables, and the impact on the apl syntax is minimal. the mechanism has the potential to allow, for example, session managers, editors, and event--- handling support to be implemented in a natural way through conventional apl programming. such facilities will therefore enjoy an entirely new flexibility and open- endedness, not seen in comparative proposals, which usually depend for their realisation on new apllansguage constructs.  karl soop
apl tools and techniques and their effect on good programming style  what is style? we know that it certianly is not confined to any specific field. instead, it applies to all creative endeavors, programming being one of those endeavors. however, before i describe style relative to writing programs, i want to discuss something with which we are all more familiar - style as it relates to writing prose since almost all of us have, at one time or another, studied literature and writing styles. what makes one author's works great and another's mediocre or poor? some may say good advertising or public whims - and sometimes this may seem true; however, good writing style is the real reason. and, you may ask, 'what factors make up writing style?'  thomas w. cook
contemporary software development environments  there are a wide variety of software development tools and methods currently available or which could be built using current research and technology. these tools and methods can be organized into four software development environments, ranging in complexity from a simple environment containing few automated tools or expensive methods to a complete one including many automated tools and built around a software engineering database. the environments were designed by considering the life-cycle products generated during two classes of software development projects. relative cost figures for the environments are offered and related issues, such as standardization, effectiveness, and impact, then addressed.  william e. howden
space-efficient closure representations  many modern compilers implement function calls (or returns) in two steps: first, a closure environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a "jump with arguments (or results)". closure conversion, which decides where and how to represent closures at runtime, is a crucial step in compilation of functional languages. we have a new algorithm that exploits the use of compile-time control and data flow information to optimize closure representations. by extensive closure sharing and allocating as many closures in registers as possible, our new closure conversion algorithm reduces heap allocation by 36% and memory fetches for local/global variables by 43%; and improves the already-efficient code generated by the standard ml of new jersey compiler by about 17% on a decstation 5000. moreover, unlike most other approaches, our new closure allocation scheme satisfies the strong "safe for space complexity" rule, thus achieving good asymptotic space usage.  zhong shao andrew w. appel
distributed algorithms visualisation for educational purposes we present our work on building interactive continuous visualisations of distributed algorithms for educational purposes. the animations are comprised by a set of visualisation windows. the visualisation windows are designed so that they demonstrate i) the different behaviours of the algorithms while running in different systems, ii) the different behaviours that the algorithms exhibit under different timing and workload of the system iii) the time and space complexities of the algorithms and iv) the "key ideas" of the functionality of the algorithms. visualisations have been written for a set of lo algorithms that are tought in a distributed algorithms advanced undergraduate course. boris koldehofe marina papatriantafilou philippas tsigas
spades - a specification and design system and its graphical interface  spades is a specification system consisting of a method, a language, and a set of tools. these components are based on a set of concepts, which forms its abstract kernel. spades supports the specification of software systems, in particular of real time software. the system to be developed is modelled using the entity-relationship-concept. while this seems to be the best way for storing specifications in a computer, it does not automatically lead to representations equally comfortable for humans. this is why spades, which has been available for some time, has recently been extended by a graphical interface. this paper gives a brief survey of the system, in particular of its new component.  j. ludewig m. glinz h. huser g. matheis h. matheis m. f. schmidt