Projects per year
Abstract
We use the control features of continuation models to interpret proofs in first-order classical theories. This interpretation is suitable for extracting algorithms from proofs of Π02 formulas. It is fundamentally different from the usual direct interpretation, which is shown to be equivalent to Friedman's trick. The main difference is that atomic formulas and natural numbers are interpreted as distinct objects. Nevertheless, the control features inherent to the continuation models permit extraction using a special "channel" on which the extracted value is transmitted at toplevel without unfolding the recursive calls. We prove that the technique fails in Scott domains, but succeeds in the refined setting of Laird's bistable bicpos, as well as in game semantics.
Original language | English |
---|---|
Title of host publication | Leibniz International Proceedings in Informatics, LIPIcs, 2016 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Pages | 13.1-13.17 |
Number of pages | 17 |
Volume | 52 |
ISBN (Print) | 9783959770101 |
DOIs | |
Publication status | Published - 1 Jun 2016 |
Event | 1st International Conference on Formal Structures for Computation and Deduction, FSCD 2016 - Porto, Portugal Duration: 22 Jun 2016 → 26 Jun 2016 |
Conference
Conference | 1st International Conference on Formal Structures for Computation and Deduction, FSCD 2016 |
---|---|
Country/Territory | Portugal |
City | Porto |
Period | 22/06/16 → 26/06/16 |
Keywords
- Classical logic
- Control operators
- Extraction
- Game semantics
Fingerprint
Dive into the research topics of 'Classical extraction in continuation models'. Together they form a unique fingerprint.Projects
- 2 Finished
-
Semantic Types for Verified Program Behaviour
Laird, J. (PI)
Engineering and Physical Sciences Research Council
28/02/14 → 31/07/17
Project: Research council
-
Semantic Structures for Higher-Order Information Flow
Laird, J. (PI)
Engineering and Physical Sciences Research Council
20/06/10 → 19/06/12
Project: Research council