Opening book details…
Can I read Practical Program Extraction from Classical Proofs on EtoBox?
Practical Program Extraction from Classical Proofs by Yevgeniy Makarov is a Computer Science article available to read on EtoBox.
What is Practical Program Extraction from Classical Proofs about?
It is well-known that a constructive proof of a Π 0 2 formula F written as a λ-term via Curry-Howard isomorphism, computes a function that witnesses F . Murthy [14] outlined an extension of this result to classical logic, with the double-negation rule mapped to Felleisen's control operator C [9]. Since C is similar to call/cc operator in Scheme and SML/NJ, this opens a possibility of extracting programs in these languages from classical proofs. However, even though the basic idea has appeared in the literature, there appears to be little work that uses Griffin's extension of the Curry-Howard isomorphism to extract practical programs in real programming languages. In this article, we fill in missing steps in Murthy's argument and extend his method to encompass more interesting proofs by allowing additional ubiquitous inference rules: equality rules, rules for atomic formulas (such as transitivity of ≤), and rules for pairs of dual decidable atoms (such as ≤ and >). We illustrate the usefulness of this extension with a complete example of program extraction.
Who reads Practical Program Extraction from Classical Proofs?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Yevgeniy Makarov
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV; Amsterdam: Elsevier BV (ISSN 1571-0661)
- Published
- 2006
- Language
- EN
- Field
- Computer Science (Physical Sciences)