eCommons

 

Extracting Efficient Code From Constructive Proofs

Other Titles

Abstract

Extraction is a technique for producing verified programs. A proof of chi:T\ldoty:T′\ldotF corresponds to a function f of type TT that maps every χ of type T to a y of type T such that F is true. If the proof is constructive, then f is recursive. The semantics of extracted code involves the manipulation of justifications, which are pieces of evidence for the truth of formulas. The raw extracted code for the formula above is actually a function γ that maps χ to a pair (y,γ′), where γ is a justification that provides evidence for the truth of F. This thesis presents various ways to improve the efficiency of extracted programs. The first way uses traditional code optimizations. Though very helpful, they are no panacea. The second way involves small changes to its underlying semantics. Certain formulas, called singleton formulas, have no interesting justifications; if F is such a formula, no justification for it needs to be built, which simplifies the extracted code. The third way to improve extracted code is to add call-by-reference parameters to it. As originally defined, extracted code passes arguments by value, which leads to inefficient code for mutable objects like arrays: passing an array by value requires making a copy of it. Adding call-by-reference parameters entails adding a state to the semantics of extracted code, which in turn leads to various semantic and syntactic design issues, like aliasing and side-effects. To account for these changes, the constructive logic used to build proofs is modified. A proof of quicksort illustrates the functional, assignment-free, side-effect-free style of proof promoted by the new logic. To relieve the user of some of the mental overhead involved in using the new logic, an array inferencing algorithm is presented. The algorithm allows users to get code that uses arrays from proofs that reason about and manipulate lists in restricted ways. In this way, users can view the use of arrays as an optimization.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1986-06

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-757

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record