Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Formal Methods for Automated Program Improvement


Madden,  Peter
Programming Logics, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Madden, P. (1994). Formal Methods for Automated Program Improvement. In B. Nebel, & L. Dreschler-Fischer (Eds.), KI-94: Advances in Artificial Intelligence. Proceedings of the 18th German Annual Conference on Artificial Intelligence (pp. 367-378). Berlin, Germany: Springer.

Cite as:
Systems supporting the manipulation of non-trivial program code are complex and are at best semi-automatic. However, formal methods, and in particular theorem proving, are providing a growing foundation of techniques for automatic program development (synthesis, improvement, transformation and verification). In this paper we report on novel research concerning: (1) the exploitation of synthesis proofs for the purposes of automatic program optimization by the transformation of proofs, and; (2) the automatic synthesis of efficient programs from standard equational definitions. A fundamental theme exhibited by our research is that mechanical program construction, whether by direct synthesis or transformation, is tantamount to program verification plus higher-order reasoning. The exploitation of the proofs-as-programs paradigm lends our approach numerous advantages over more traditional approaches to program improvement. For example, we are able to automate the identification of efficient recursive data-types which usually correspond to *eureka* steps in ``pure'' transformational techniques such as unfold/fold. Furthermore, all transformed, and synthesized, programs are guaranteed correct with respect to their specifications.