English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  A General Technique for Automatically Optimizing Programs through the Use of Proof Plans

Madden, P., & Green, I. (1995). A General Technique for Automatically Optimizing Programs through the Use of Proof Plans. In J. Calmet, & J. A. Campbell (Eds.), Integrating Symbolic Mathematical Computation and Artificial Intelligence (pp. 64-79). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-ACE1-9 Version Permalink: https://hdl.handle.net/21.11116/0000-000E-587E-3
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://rdcu.be/dxDRC (Publisher version)
Description:
-
OA-Status:
Not specified

Creators

show
hide
 Creators:
Madden, Peter1, Author           
Green, Ian2, Author
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-121995
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 519535
Other: Local-ID: C1256104005ECAFC-691B88F59B0C617EC125614400622B5B-MaddenGreen94b-aismc2
DOI: 10.1007/3-540-60156-2_6
BibTex Citekey: Madden-Green_AISMC94
 Degree: -

Event

show
hide
Title: Second International Conference on Integrating Symbolic Mathematical Computation and Artificial Intelligence
Place of Event: Cambridge, UK
Start-/End Date: 1994-08-03 - 1994-08-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: Integrating Symbolic Mathematical Computation and Artificial Intelligence
  Subtitle : Second International Conference, AISMC-2, Cambridge, United Kingdom, August 3-5, 1994. Selected Papers
  Abbreviation : AISMC 1994
Source Genre: Proceedings
 Creator(s):
Calmet, Jacques1, Editor
Campbell, John A.1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 64 - 79 Identifier: ISBN: 978-3-540-60156-2

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 958 Sequence Number: - Start / End Page: - Identifier: -