Improvement Theory and Its Applications. Sands, D. In Gordon, A. D. & Pitts, A. M., editors, Higher Order Operational Techniques in Semantics, of Publications of the Newton Institute, pages 275--306. Cambridge University Press, 1998.
Improvement Theory and Its Applications [pdf]Paper  abstract   bibtex   
An improvement theory is a variant of the standard theories of observational approximation (or equivalence) in which the basic observations made of a functional program's execution include some intensional information about, for example, the program's computational cost. One program is an improvement of another if its execution is more efficient in any program context. In this article we give an overview of our work on the theory and applications of improvement. Applications include reasoning about time properties of functional programs, and proving the correctness of program transformation methods. We also introduce a new application, in the form of some bisimulation-like proof techniques for equivalence, with something of the flavour of Sangiorgi's ``bisimulation up-to expansion and context''.

Downloads: 0