Type-alpha DPLs
This paper introduces Denotational Proof Languages (DPLs). DPLs are languages for presenting, discovering, and checking formal proofs. In particular, in this paper we discus type-alpha DPLs---a simple class of DPLs for which termination is guaranteed and proof checking can be performed in time lin...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/6661 |
| _version_ | 1826200443720564736 |
|---|---|
| author | Arkoudas, Konstantine |
| author_facet | Arkoudas, Konstantine |
| author_sort | Arkoudas, Konstantine |
| collection | MIT |
| description | This paper introduces Denotational Proof Languages (DPLs). DPLs are languages for presenting, discovering, and checking formal proofs. In particular, in this paper we discus type-alpha DPLs---a simple class of DPLs for which termination is guaranteed and proof checking can be performed in time linear in the size of the proof. Type-alpha DPLs allow for lucid proof presentation and for efficient proof checking, but not for proof search. Type-omega DPLs allow for search as well as simple presentation and checking, but termination is no longer guaranteed and proof checking may diverge. We do not study type-omega DPLs here. We start by listing some common characteristics of DPLs. We then illustrate with a particularly simple example: a toy type-alpha DPL called PAR, for deducing parities. We present the abstract syntax of PAR, followed by two different kinds of formal semantics: evaluation and denotational. We then relate the two semantics and show how proof checking becomes tantamount to evaluation. We proceed to develop the proof theory of PAR, formulating and studying certain key notions such as observational equivalence that pervade all DPLs. We then present NDL, a type-alpha DPL for classical zero-order natural deduction. Our presentation of NDL mirrors that of PAR, showing how every basic concept that was introduced in PAR resurfaces in NDL. We present sample proofs of several well-known tautologies of propositional logic that demonstrate our thesis that DPL proofs are readable, writable, and concise. Next we contrast DPLs to typed logics based on the Curry-Howard isomorphism, and discuss the distinction between pure and augmented DPLs. Finally we consider the issue of implementing DPLs, presenting an implementation of PAR in SML and one in Athena, and end with some concluding remarks. |
| first_indexed | 2024-09-23T11:36:33Z |
| id | mit-1721.1/6661 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:36:33Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/66612019-04-11T02:52:46Z Type-alpha DPLs Arkoudas, Konstantine AI Deduction formal proofs semantics proof checking soundness logic This paper introduces Denotational Proof Languages (DPLs). DPLs are languages for presenting, discovering, and checking formal proofs. In particular, in this paper we discus type-alpha DPLs---a simple class of DPLs for which termination is guaranteed and proof checking can be performed in time linear in the size of the proof. Type-alpha DPLs allow for lucid proof presentation and for efficient proof checking, but not for proof search. Type-omega DPLs allow for search as well as simple presentation and checking, but termination is no longer guaranteed and proof checking may diverge. We do not study type-omega DPLs here. We start by listing some common characteristics of DPLs. We then illustrate with a particularly simple example: a toy type-alpha DPL called PAR, for deducing parities. We present the abstract syntax of PAR, followed by two different kinds of formal semantics: evaluation and denotational. We then relate the two semantics and show how proof checking becomes tantamount to evaluation. We proceed to develop the proof theory of PAR, formulating and studying certain key notions such as observational equivalence that pervade all DPLs. We then present NDL, a type-alpha DPL for classical zero-order natural deduction. Our presentation of NDL mirrors that of PAR, showing how every basic concept that was introduced in PAR resurfaces in NDL. We present sample proofs of several well-known tautologies of propositional logic that demonstrate our thesis that DPL proofs are readable, writable, and concise. Next we contrast DPLs to typed logics based on the Curry-Howard isomorphism, and discuss the distinction between pure and augmented DPLs. Finally we consider the issue of implementing DPLs, presenting an implementation of PAR in SML and one in Athena, and end with some concluding remarks. 2004-10-08T20:36:40Z 2004-10-08T20:36:40Z 2001-10-05 AIM-2001-025 http://hdl.handle.net/1721.1/6661 en_US AIM-2001-025 27 p. 1766438 bytes 815435 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | AI Deduction formal proofs semantics proof checking soundness logic Arkoudas, Konstantine Type-alpha DPLs |
| title | Type-alpha DPLs |
| title_full | Type-alpha DPLs |
| title_fullStr | Type-alpha DPLs |
| title_full_unstemmed | Type-alpha DPLs |
| title_short | Type-alpha DPLs |
| title_sort | type alpha dpls |
| topic | AI Deduction formal proofs semantics proof checking soundness logic |
| url | http://hdl.handle.net/1721.1/6661 |
| work_keys_str_mv | AT arkoudaskonstantine typealphadpls |