Although software inspection has led to improvements in software quality, many software systems continue to be deployed with unacceptable numbers of errors, even when software inspection is part of the development process. The difficulty of manually verifying that the software under inspection conforms to the rules is partly to blame. We describe the design and implementation of a tool designed to help alleviate this problem. The tool provides mechanisms for fine-grained inspection of software by exposing the results of sophisticated whole-program static analysis to the inspector. The tool computes many static-semantic representations of the program, including an accurate call graph and dependence graph. A whole-program pointer analysis is used to make sure that the representation is precise with respect to aliases induced by pointer usage. Views on the dependence graph and related representations are supported. Queries on the dependence graph allow an inspector to answer detailed questions about the semantics of the program. Facilities for openness and extensibility permit the tool to be integrated with many software development processes. The main challenge of the approach is to provide facilities to navigate and manage the enormous complexity of the dependence graph.

A systematic approach is given for deriving incremental programs that exploit caching. The cache-and-prune method presented in the article consists of three stages: (I) the original program is extended to cache the results of all its intermediate subcomputations as well as the final result, (II)) the extended program is incrementalized so that computation on a new input can use all intermediate results on an old input, and (III) unused results cached by the extended program and maintained by the incremental program are pruned away, leaving a pruned extended program that caches only useful intermediate results and a pruned incremental program that uses and maintains only useful results. All three stages utilize static analyses and semantics-preserving transformations. Stages I and III are simple, clean, and fully automatable. The overall method has a kind of optimality with respect to the techniques used in Stage II. The method can be applied straightfowardly to provide a systematic approach to program improvement via caching.

This paper presents program analyses and transformations that discover a general class of auxiliary information for any incremental computation problem. Combining these techniques with previous techniques for caching intermediate results, we obtain a systematic approach that transforms nonincremental programs into efficient incremental programs that use and maintain useful auxiliary information as well as useful intermediate results. The use of auxiliary information allows us to achieve a greater degree of incrementality than otherwise possible. Applications of the approach include strength reduction in optimizing compilers and finite differencing in transformational programming.

A systematic approach is given for symbolically caching intermediate results useful for deriving incremental programs from non-incremental programs. Our method can be applied straightforwardly to provide a systematic approach to program improvement via caching. 1 Introduction Incremental programs take advantage of repeated computations on inputs that differ only slightly from one another, making use of the old output in computing a new output rather than computing from scratch. Methods of incremental computation have widespread application, e.g., optimizing compilers [2, 9, 11], transformational programming [30, 33, 43], interactive editing systems [4, 39], etc. Deriving incremental programs. Given a program f and an input change \\Phi, a program f 0 that computes the result of f(x \\Phi y) efficiently by making use of the value of f(x) is called an incremental version of f under \\Phi. Liu and Teitelbaum [27] give a systematic transformational approach for deriving an incremental p...

A systematic approach is given for deriving incremental programs from non-incremental programs written in a standard functional programming language. We exploit a number of program analysis and transformation techniques and domain-specific knowledge, centered around effective utilization of caching, in order to provide a degree of incrementality not otherwise achievable by a generic incremental evaluator.

Article Free Access Share on Higher-order attribute grammars and editing environments Authors: Tim Teitelbaum Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile , Richard Chapman Department of Computer Science, Cornell University, Ithaca, NY Department of Computer Science, Cornell University, Ithaca, NYView Profile Authors Info & Claims PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementationJune 1990 Pages 197–208https://doi.org/10.1145/93542.93567Published:01 June 1990Publication History 17citation435DownloadsMetricsTotal Citations17Total Downloads435Last 12 Months20Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Incremental computation via function caching Authors: W. Pugh Dept. of Computer Science, Cornell University, Ithaca, NY and Dept. of Comp. Sci., Univ. of Maryland, College Park, Md. Dept. of Computer Science, Cornell University, Ithaca, NY and Dept. of Comp. Sci., Univ. of Maryland, College Park, Md.View Profile , T. Teitelbaum Dept. of Computer Science, Cornell University, Ithaca, NY Dept. of Computer Science, Cornell University, Ithaca, NYView Profile Authors Info & Claims POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1989 Pages 315–328https://doi.org/10.1145/75277.75305Published:03 January 1989Publication History 138citation969DownloadsMetricsTotal Citations138Total Downloads969Last 12 Months130Last 6 weeks25 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A major drawback to the use of attribute grammars in language-based editors has been that attributes can only depend on neighboring attributes in a program's syntax tree. This paper concerns new attribute-grammar-based methods that, for a suitable class of grammars, overcome this fundamental limitation. The techniques presented allow the updating algorithm to skip over arbitrarily large sections of the tree that more straightforward updating methods visit node by node. These techniques are then extended to deal with aggregate values, so that the attribute updating procedure need only follow dependencies due to a changed component of an aggregate value. Although our methods work only for a restricted class of attribute grammars, satisfying the necessary restrictions should not place an undue burden on the writer of the grammar.

The ability to generate language-based editors depends on the existence of a powerful, language-independent model of editing. A model is proposed in which programs are represented as attributed abstract-syntax trees with an associated relational database. Relations can depend on the state of the attributed tree, and attributes can depend on the values in relations, provided there are no circular dependencies. The power and the limitations of relational operations are demonstrated with respect to the support of static-semantic checking, anomaly detection, an interrogation facility, and the ability to define alternative program displays. The advantages of the hybrid system over both the purely relational and purely attribute-based systems are presented, and new algorithms are given for query evaluation and incremental view updating motivated by the efficiency requirements of interactive editing under the defined model. A prototype implementation of an editor generator is described, and suggestions for future research are made.

Knowledge of a programming language's grammar allows language-based editors to enforce syntactic correctness at all times during development by restricting editing operations to legitimate modifications ot ~ the program's context-free derivation tree; however, not all language constraints can be enforced in this way because not all features can be described by the context-free formalism.Attribute grammars permit context-dependent language features to be expressed in a modular, declarative fashion and thus are a good basis for specifying language-based editors.Such editors represent programs as attributed trees, Which are modified by operations such as subtree pruning and grafting.Incremental analysis is performed by updating attribute values after every modification.This paper discusses how updating can be carried out and presents several algorithms for the task, including one that is asymptotically optimal in time.

A syntax-directed editor is a tool for structured program development. Such an editor can enforce syntactic correctness incrementally by restricting editing operations to legitimate modifications of the program's context-free derivation tree. However, not all language features can be described by the context-free formalism. To build editors that enforce non-context-free correctness, a more powerful specification technique is needed. In this paper we discuss the advantages of attribute grammars as a specification technique for a syntax-directed editing system. We also present an efficient algorithm for incrementally evaluating attributes as a program tree is derived.