Extracting Efficient Code From Constructive Proofs

Other Titles


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



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


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)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record