Extracting Efficient Code From Constructive Proofs

dc.contributor.authorSasaki, James T.en_US
dc.description.abstractExtraction is a technique for producing verified programs. A proof of $\forall chi : T \ldot \exists y : T' \ldot F$ corresponds to a function $f$ of type $T \rightarrow T'$ that maps every $\chi$ 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 $\gamma$ that maps $\chi$ to a pair $(y, \gamma')$, where $\gamma'$ 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.en_US
dc.format.extent10831480 bytes
dc.format.extent3470019 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleExtracting Efficient Code From Constructive Proofsen_US
dc.typetechnical reporten_US


Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
10.33 MB
Adobe Portable Document Format
No Thumbnail Available
3.31 MB
Postscript Files