Software developers must modify their programs to keepup with changing requirements and designs. Often, aconceptually simple change can require numerous editsthat are similar but not identical, leading to errors andomissions. Researchers have designed programming environmentsto address this problem, but most of thesesystems are counter-intuitive and difficult to use.By applying a task-centered design process, we developeda visual tool that allows programmers to makecomplex code transformations in an intuitive manner.This approach uses a representation that aligns wellwith programmers' mental models of programming structures.The visual language combines textual and graphicalelements and is expressive enough to support a broadrange of code-changing tasks. To simplify learning thesystem, its user interface scaffolds construction and executionof transformations. An evaluation with Java programmerssuggests that the interface is intuitive, easyto learn, and effective on a representative editing task.

Implementing large and sweeping changes to software source code can be tedious and error-prone. A conceptually simple change may require a significant code editing effort. Integrating scriptable source-to-source program transformations into development environments can assist developers with this task. We present a developer-oriented interactive source code transformation tool for Java that addresses this need.

Programmers who suffer from repetitive stress injuries find it difficult to program by typing. Speech interfaces can reduce the amount of typing, but existing programming-by-voice tools make it awkward for programmers to enter and edit program text. We used a human-centric approach to address these problems. We first studied how programmers verbalize code, and found that spoken programs contain lexical, syntactic and semantic ambiguities that do not appear in written programs. Using the results from this study, we designed Spoken Java, a syntactically similar, yet semantically identical variant of Java that is easier to speak. We built an Eclipse IDE plug-in called SPEED (for speech editor) to support the combination of Spoken Java and an associated command language. In this paper, we report the results of the first study ever of any working programming-by-voice system. Our evaluation with expert Java developers showed that most developers had little trouble learning to use the system via spoken commands, but were reluctant to speak literal code out loud. As expected, programmers found programming by voice to be slower than typing

Programmers who suffer from repetitive stress injuries find it difficult to spend long amounts of time typing code. Speech interfaces can help developers reduce their dependence on typing. However, existing programming by voice techniques make it awkward for programmers to enter and edit program text. To design a better alternative, we conducted a study to learn how software developers naturally verbalize programs. We found that spoken programs are different from written programs in ways similar to the differences between spoken and written English; spoken programs contain lexical, syntactic and semantic ambiguities that do not appear in written programs. Using the results from this study, we designed Spoken Java, a semantically identical variant of Java that is easier to say out loud. Using Spoken Java, software developers can speak more naturally by verbalizing their program code as if they were reading it out loud. Spoken Java is analyzed by extending a conventional Java programming language analysis engine written in our Harmonia program analysis framework to support the kinds of ambiguities that arise from speech.

We present Linked Editing, a novel, lightweight editor-based technique for managing duplicated source code. Linked Editing is implemented in a prototype editor called Codelink. We argue that the use of programming abstractions like functions and macros-the traditional solution to duplicated code-has inherent cognitive costs, leading programmers to chronically copy and paste code instead. Our user study compares functional abstraction with Linked Editing and shows that Linked Editing can give the benefits of abstraction with orders of magnitude decrease in programming time.

A packet filter is a programmable selection criterion for classifying or selecting packets from a packet stream in a generic, reusable fashion. Previous work on packet filters falls roughly into two categories, namely those efforts that investigate flexible and extensible filter abstractions but sacrifice performance, and those that focus on low-level, optimized filtering representations but sacrifice flexibility. Applications like network monitoring and intrusion detection, however, require both high-level expressiveness and raw performance. In this paper, we propose a fully general packet filter framework that affords both a high degree of flexibility and good performance. In our framework, a packet filter is expressed in a high-level language that is compiled into a highly efficient native implementation. The optimization phase of the compiler uses a flowgraph set relation called edge dominators and the novel application of an optimization technique that we call "redundant predicate elimination," in which we interleave partial redundancy elimination, predicate assertion propagation, and flowgraph edge elimination to carry out the filter predicate optimization. Our resulting packet-filtering framework, which we call BPF+, derives from the BSD packet filter (BPF), and includes a filter program translator, a byte code optimizer, a byte code safety verifier to allow code to migrate across protection boundaries, and a just-in-time assembler to convert byte codes to efficient native code. Despite the high degree of flexibility afforded by our generalized framework, our performance measurements show that our system achieves performance comparable to state-of-the-art packet filter architectures and better than hand-coded filters written in C.

The task of mapping between source programs and machine code, once the code has been optimized and transformed by a compiler is often difficult. Yet there are many instances, such as debugging optimized code or attributing performance analysis data to source lines, whrn it is useful or necessary to understand at the source level what is occurring in the binary. The standard approach has been for tools to attempt to map directly from the optimized binary to the original source. Such mappings are often fragile, and sometimes inaccurate or misleading. We suggest an alternative approach. Rather than mapping directly between the original source and the binary, we create a modified version of the source program, still recognizable, but updated to reflect some of the effects of optimizations, thus facilitating mapping from the binary. We have implemented a tool, Optview, to demonstrate and test these ideas.

Titanium is a language and system for high-performance parallel scientific computing. Titanium uses Java as its base, thereby leveraging the advantages of that language and allowing us to focus attention on parallel computing issues. The main additions to Java are immutable classes, multidimensional arrays, an explicitly parallel SPMD model of computation with a global address space, and zone-based memory management. We discuss these features and our design approach, and report progress on the development of Titanium, including our current driving application: a three-dimensional adaptive mesh refinement parallel Poisson solver. © 1998 John Wiley & Sons, Ltd.

Previously published algorithms for LR ( k ) incremental parsing are inefficient, unnecessarily restrictive, and in some cases incorrect. We present a simple algorithm based on parsing LR( k ) sentential forms that can incrementally parse an arbitrary number of textual and/or structural modifications in optimal time and with no storage overhead. The central role of balanced sequences in achieving truly incremental behavior from analysis algorithms is described, along with automated methods to support balancing during parse table generation and parsing. Our approach extends the theory of sentential-form parsing to allow for ambiguity in the grammar, exploiting it for notational convenience, to denote sequences, and to construct compact (“abstract”) syntax trees directly. Combined, these techniques make the use of automatically generated incremental parsers in interactive software development environments both practical and effective. In addition, we address information preservation in these environments: Optimal node reuse is defined; previous definitions are shown to be insufficient; and a method for detecting node reuse is provided that is both simpler and faster than existing techniques. A program representation based on self-versioning documents is used to detect changes in the program, generate efficient change reports for subsequent analyses, and allow the parsing transformation itself to be treated as a reversible modification in the edit log.

A major research goal for compilers and environments is the automatic derivation of tools from formal specifications. However, the formal model of the language is often inadequate; in particular, LR(k) grammars are unable to describe the natural syntax of many languages, such as C++ and Fortran, which are inherently non-deterministic. Designers of batch compilers work around such limitations by combining generated components with ad hoc techniques (for instance, performing partial type and scope analysis in tandem with parsing). Unfortunately, the complexity of incremental systems precludes the use of batch solutions. The inability to generate incremental tools for important languages inhibits the widespread use of language-rich interactive environments.We address this problem by extending the language model itself, introducing a program representation based on parse dags that is suitable for both batch and incremental analysis. Ambiguities unresolved by one stage are retained in this representation until further stages can complete the analysis, even if the reaolution depends on further actions by the user. Representing ambiguity explicitly increases the number and variety of languages that can be analyzed incrementally using existing methods.To create this representation, we have developed an efficient incremental parser for general context-free grammars. Our algorithm combines Tomita's generalized LR parser with reuse of entire subtrees via state-matching. Disambiguation can occur statically, during or after parsing, or during semantic analysis (using existing incremental techniques); program errors that preclude disambiguation retsin multiple interpretations indefinitely. Our representation and analyses gain efficiency by exploiting the local nature of ambiguities: for the SPEC95 C programs, the explicit representation of ambiguity requires only 0.5% additional space and less than 1% additional time during reconstruction.

Determining the relative execution frequency of program regions is essential for many important optimization techniques, including register allocation, function inlining, and instruction scheduling. Estimates derived from profiling with sample inputs are generally regarded as the most accurate source of this information; static (compile-time) estimates are considered to be distinctly inferior. If static estimates were shown to be competitive, however, their convenience would outweigh minor gains from profiling, and they would provide a sound basis for optimization when profiling is impossible.

Using the simple tree attributions described in this paper, attribute values can themselves be trees, enabling attribution to be used for tree transformations. Unlike higher-order attribute grammars, simple tree attributions have the property of descriptional composition, which allows a complex transformation to be built up from simpler ones, yet be executed efficiently. In contrast to other formalisms that admit descriptional composition, notably composable attribute grammars, simple tree attributions have the expressive power to handle remote references and recursive syntactic (tree-generating) functions, providing significantly more general forms of attribution and transformation.

Many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. The traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. This paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible.

A data breakpoint associates debugging actions with programmer-specified conditions on the memory state of an executing program. Data breakpoints provide a means for discovering program bugs that are tedious or impossible to isolate using control breakpoints alone. In practice, programmers rarely use data breakpoints, because they are either unimplemented or prohibitively slow in available debugging software. In this paper, we present the design and implementation of a practical data breakpoint facility.

One way to provide fault isolation among cooperating software modules is to place each in its own address space. However, for tightly-coupled modules, this solution incurs prohibitive context switch overhead. In this paper, we present a software approach to implementing fault isolation within a single address space.Our approach has two parts. First, we load the code and data for a distrusted module into its own fault do main, a logically separate portion of the application's address space. Second, we modify the object code of a distrusted module to prevent it from writing or jumping to an address outside its fault domain. Both these software operations are portable and programming language independent.Our approach poses a tradeoff relative to hardware fault isolation: substantially faster communication between fault domains, at a cost of slightly increased execution time for distrusted modules. We demonstrate that for frequently communicating modules, implementing fault isolation in software rather than hardware can substantially improve end-to-end application performance.

Powerful editing systems for developing complex software documents are difficult to engineer. Besides requiring efficient incremental algorithms and complex data structures, such editors must accommodate flexible editing styles, provide a consistent, coherent, and powerful user interface, support individual variations and projectwide configurations, maintain a sharable database of information concerning the documents being edited, and integrate smoothly with the other tools in the environment. Pan is a language-based editing and browsing system that exhibits these characteristics. This paper surveys the design and engineering of Pan , paying particular attention to a number of issues that pervade the system: incremental checking and analysis, information retention in the presence of change, tolerance for errors and anomalies, and extension facilities.

Processors for programming languages and other formal languages typically use a concrete syntax to describe the user's view of a program and an abstract syntax to represent language structures internally. Grammatical abstraction is defined as a relationship between two context-free grammars. It formalizes the notion of one syntax being “more abstract” than another. Two variants of abstraction are presented. Weak grammatical abstraction supports (i) the construction during LR parsing of an internal representation that is closely related to the abstract syntax and (ii) incremental LR parsing using that internal representation as its base. Strong grammatical abstraction tightens the correspondence so that top-down construction of incrementally-parsable internal representations is possible. These results arise from an investigation into language-based editing systems, but apply to any program that transforms a linguistic object from a representation in its concrete syntax to a representation in its abstract syntax or vice versa.

A Rewrite System is a collection of rewrite rules of the form α β where α and β are tree patterns. A rewrite system can be extended by associating a cost with each rewrite rule, and by defining the cost of a rewrite sequence as the sum of the costs of all the rewrite rules in the sequence. The REACHABILITY problem for a rewrite system R is, given an input tree T and a fixed goal tree G, to determine if there exists a rewrite sequence in R, rewriting T into G and, if so, to obtain one such sequence. The C-REACHABILITY problem is similar except that the obtained sequence must have minimal cost among all those sequences writing T into G.

Abstract In modular programs, groups of routines constitute conceptual abstractions. A method for providing execution profiles for such programs is presented. The central idea is that the execution time for a routine is charged to the routines that call it. The implementation of this method by a profiler called gprof is described. The techniques used to gather the necessary information about the timing and structure of the program are given, as is the processing used to propagate routine execution times along arcs of the call graph of the program. The method for displaying the profile to the user is discussed. Experience using the profiles for hand‐tuning large programs is summarized. Additional uses for the profiles are suggested.

A new algorithm for recognizing and parsing arbitrary context-free languages is presented, and several new results are given on the computational complexity of these problems. The new algorithm is of both practical and theoretical interest. It is conceptually simple and allows a variety of efficient implementations, which are worked out in detail. Two versions are given which run in faster than cubic time. Surprisingly close connections between the Cocke-Kasami-Younger and Earley algorithms are established which reveal that the two algorithms are “almost” identical.

An algorithm is given to translate a relatively low-level intermediate representation of a program into assembly code or machine code for a target computer. The algorithm is table driven. A construction algorithm is used to produce the table from a functional description of the target machine. The method produces high quality code for many commercially available computers. By replacing the table, it is possible to retarget a compiler for another kind of computer. In addition techniques are given to prove the correctness of the translator.

Three ACM symposia on Principles of Programming Languages, jointly sponsored by SIGACT and SIGPLAN, have now been held. The first symposium was in October 1973, the second in January 1975, and the third the following year. It is now planned that the symposia be held annually. The fourth symposium is scheduled for January 17-19, 1977, in Los Angeles. Four of the twenty papers presented at the third symposium have been selected for publication in this special section. 1 Each paper was refereed in the customary fashion and each of the papers appearing here is a revised or extended version of the original paper or extended abstract included in the Conference Record. The papers address a variety of topics, yet they have in common a blend of both theoretical and pragmatic considerations. Two of the papers discuss techniques for program transformations. (Indeed, program transformation was an important theme at the symposium.) Baker presents an algorithm for transforming a program in which the flow of control may not be represented by structured-programming-style syntax into a computationally equivalent program which is more readable because the iterative and conditional structure is explicit. An implementation of the technique is described in which Fortran programs are transformed to a structured Fortran dialect. The paper by Loveman discusses the transformation of programs to equivalent programs in the same language which require less running time and/or less space. He illustrates a number of these transformations and describes several programming systems in which the source-to-source techniques have been used. He also argues that appropriate source-to-source transformations can be used to transform a program to a form in which a straightforward code generator could produce the sort of code now generated by conventional optimizing compilers. Such a technique would simplify the code generation phase of a compiler and would provide the programmer with a source-level description of the optimized program. A different aspect of code generation is the topic of the paper by Aho, Johnson, and Ullman. They study the problem of generating good machine code for so-called straight line source code which contains common subexpressions (i.e. multiple occurrences of the same variables or expressions). They show that under a variety of assumptions, the generation of optimal code sequences is computationally difficult in a certain sense. An analysis of some heuristics for code generation is given which offers insight into the reasons for the complexity and some approaches to generating reasonable code sequences at an acceptable cost. Unlike the other papers, all of which, in some sense, give methods for creating programs from other programs, the paper by Summers investigates methods for creating programs from examples of their behavior. An implementation is described in which, by exploiting the structure embodied in S-expressions, programs in a subset of LISP are synthesized from pairs of S-expressions. In order to achieve timely publication of a special section such as this one, it was necessary to set deadlines for each stage in the process. The cooperation of the authors, the referees, and the editors in meeting these deadlines is gratefully acknowledged.

A new on-line context free language recognition algorithm is presented which is derived from Earley's algorithm and has several advantages over the original. First, the new algorithm not only is conceptually simpler than Earley's, but also allows significant speed improvements. Second, our algorithm serves to explain the connections between Earley's algorithm and the Cocke-Kasami-Younger algorithm. Third, our algorithm allows an implementation which uses only 0(n2/log n) operations on bit vectors of length n, or 0(n3/log n) operations on a RAM. This makes it the fastest known on-line context free language recognition algorithm.

A new algorithm for global flow analysis on reducible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst-case time bound of O ( e log e ) function operations. It is also shown that in programming terms, the number of operations is proportional to e plus the number of exits from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. The algorithm can be extended to yet larger classes of function spaces and graphs by relaxing the time bound. Examples are given of code improvement problems which can be solved using the algorithm.

A new algorithm for global flow analysis on reducible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst case time bound of 0(e log2e) function operations. In programming terms, the number of operations is shown to be proportional to e + the number of exit nodes from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. It is shown that by relaxing these time bounds, a yet wider class of function spaces can be handled.

It is shown using phrase-structure-preserving grammatical transformations that the family of $(1,1)$ bounded right context languages is the same as the family of context-free deterministic languages. The elimination of $\lambda $-rules and a reconciliation of our definition of bounded right context with Floyd’s are also discussed.

A substantial portion of any programmer's time is spent in debugging. One of the major services of any compiler ought to be to provide as much information as possible about compile-time errors in order to minimize the time required for debugging. A good error detection and recovery scheme should maximize the number of errors detected but minimize the number of times it reports an error when there is none. These spurious error detections and their associated error messages are usually engendered by an inappropriate recovery action.In this paper we describe a recovery scheme for syntax errors which provides high quality recovery with good diagnostic information at relatively low cost. In addition, implementation of the recovery scheme can be automated - that is, the recovery routine can be created by a parser-generator. Therefore, the compiler designer need not be burdened with the difficulties of error recovery and the programming effort necessary to design and debug a myriad of ad hoc recovery routines.