This paper is a progress report on our research into the problem of automatically identifying and using class invariants in object-oriented programs. We introduce an example of a class invariant in Java, and review applications for class invariants in software engineering tools and in compiler optimization. We then focus on an elementary problem of definition: what is a class invariant? This question gives an interesting perspective on programming language design. We conclude that there are many reasonable categories of class invariants, and that the problem of finding good definitions cannot be solved by a thought experiment. The only way to choose good categories is to experiment with the analysis of real programs, to see which categories of class invariant are actually useful. Our current research focuses on these experiments.

This paper presents a method called relational constraint for finding binary relations among the variables and constants of a program. The method constructs a table of binary relations and treats the program as a collection of constraints on tuples of relations in the table. An experimental optimizer called Thinner uses this method to analyze programs of size n in O(n2) time.

Article Free Access Share on The Pascal Trainer Author: Adam Brooks Webber Computer Science Department, Western Illinois University, Macomb, IL Computer Science Department, Western Illinois University, Macomb, ILView Profile Authors Info & Claims SIGCSE '96: Proceedings of the twenty-seventh SIGCSE technical symposium on Computer science educationMarch 1996 Pages 261–265https://doi.org/10.1145/236452.236552Published:01 March 1996Publication History 2citation195DownloadsMetricsTotal Citations2Total Downloads195Last 12 Months18Last 6 weeks8 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

We describe a new technique for optimizing first-order functional programs. Programs are represented as graph grammars, and optimization proceeds by counterexample: when a graph generated by the grammar is found to contain an unnecessary computation, the optimizer attempts to reformulates the grammar so that it never again generates any graph that contains that counterexample. This kind of program reformulation corresponds to an interesting problem on context-free grammars. Our reformulation technique is derived from an (approximate) solution to this CFG problem. An optimizer called Thinner is the proof of concept for this technique. Thinner is a fully automatic, source-to-source optimizer for a Lisp-like language of purely functional, first-order programs. Thinner rediscovers a wide variety of common compiler optimizations. It also finds other more exotic transformations, including the well-known Fibonacci reformulation and the Knuth-Morris-Pratt optimization.