Obvious Properties of Computer Programs

We explore the question of what properties of LISP programs can be made “obvious” to a computer system. We present a polynomial-time algorithm for inferring interesting properties of pure LISP programs. Building on previous work in knowledge representation for rapid inference, we present a language for representing properties of programs. We treat properties as generalized types, i. e. , sets of program values. The property language is expressive enough to represent any RE set of LISP values as a property, and can naturally represent, a wide variety of useful properties. We then use a general technique to construct a polynomial-time property inference relation and use type-inference style program analysis to integrate this relation into an algorithm for inferring properties of programs. This algorithm is intended to work in the context of a library of background information, most of which is typically derived from previous runs of the algorithm. Due to the expressive representation system, no algorithm can infer every valid propertyso instead of proving completeness we show our algorithm’s usefulness by giving examples of properties inferred. These examples include that insertion sort returns a sorted permutation of its input, and that a clique finding program correctly returns a clique.

Authors

• Robert Givan

Keywords

No keywords are indexed for this paper.