MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Madden, Peter
Green, Ian		dblp
dblp
Editor(s):
Calmet, Jacques
Campbell, John A.		dblp
dblp
BibTeX cite key*:
MaddenGreen94b-aismc2
Title, Booktitle
Title*:
A General Technique for Automatic Optimization by Proof Planning
Booktitle*:
Proceedings of the 2nd International Conference on Artificial Intelligence and Symbolic Mathematical Computing (AISMC-2)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
King's College, Cambridge, England
Language:
English
Event Date*
(no longer used):
August 3-5, 1994
Organization:
Event Start Date:
29 April 2024
Event End Date:
29 April 2024
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
958
Number:
Month:
Pages:
80-96
Year*:
1995
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
Note:
Also available as Research Report MPI-I-94-239, Max-Planck-Institut für Informatik, Saarbrücken. Extended version to appear in Journal of Automated Reasoning
(LaTeX) Abstract:
The use of *proof plans* -- formal patterns of reasoning for theorem proving -- to control the (automatic) synthesis of efficient programs from standard definitional equations is described. A general framework for synthesizing efficient programs, using tools such as higher-order unification, has been developed and holds promise for encapsulating an otherwise diverse, and often ad hoc, range of transformation techniques. A prototype system has been implemented. We illustrate the methodology by a novel means of affecting *constraint-based* program optimization through the use of proof plans for mathematical induction. \par Proof plans are used to control the (automatic) synthesis of functional programs, specified in a standard equational form, E, by using the proofs as programs principle. The goal is that the program extracted from a constructive proof of the specification is an optimization of that defined solely by E. Thus the theorem proving process is a form of program optimization allowing for the construction of an efficient, *target*,
program from the definition of an inefficient, *source*, program. \par The general technique for controlling the syntheses of efficient programs involves using E to specify the target program and then introducing a new sub-goal into the proof of that specification. Different optimizations are achieved by placing different characterizing restrictions on the form of this new sub-goal and hence on the subsequent proof. Meta-variables and higher-order unification are used in a technique called *middle-out reasoning* to circumvent eureka steps concerning, amongst other things, the identification of recursive data-types, and unknown constraint functions. Such problems typically require user intervention.
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:
@INPROCEEDINGS{MaddenGreen94b-aismc2,
AUTHOR = {Madden, Peter and Green, Ian},
 EDITOR = {Calmet, Jacques and Campbell, John A.},
 TITLE = {A General Technique for Automatic Optimization by Proof Planning},
 BOOKTITLE = {Proceedings of the 2nd International Conference on Artificial Intelligence and Symbolic Mathematical Computing (AISMC-2)},
 PUBLISHER = {Springer},
 YEAR = {1995},
 VOLUME = {958},
 PAGES = {80--96},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {King's College, Cambridge, England},
 NOTE = {Also available as Research Report MPI-I-94-239, Max-Planck-Institut für Informatik, Saarbrücken. Extended version to appear in Journal of Automated Reasoning},
}

Entry last modified by Uwe Brahm/MPII/DE, 03/12/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Uwe Brahm		Created
01/14/1995 06:52:16 PM
Revisions
16.
15.
14.
13.
12.		Editor(s)
Uwe Brahm/MPII/DE
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE		Edit Dates
20.03.96 15:34:31
13/12/95 12:24:05
13/12/95 10:46:21
12/12/95 15:03:20
30/11/95 09:47:26