## Mercurial > cpdt > repo

### comparison src/Intro.v @ 512:6b3fb6672cfa

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

Addressing some inaccuracies of comparison with PVS

author | Adam Chlipala <adam@chlipala.net> |
---|---|

date | Sun, 12 May 2013 12:50:27 -0400 |

parents | da576746c3ba |

children | ed829eaa91b2 |

comparison

equal
deleted
inserted
replaced

511:67d59a15b0e3 | 512:6b3fb6672cfa |
---|---|

1 (* Copyright (c) 2008-2012, Adam Chlipala | 1 (* Copyright (c) 2008-2013, Adam Chlipala |

2 * | 2 * |

3 * This work is licensed under a | 3 * This work is licensed under a |

4 * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 | 4 * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 |

5 * Unported License. | 5 * Unported License. |

6 * The license text is available at: | 6 * The license text is available at: |

88 (** ** An Easy-to-Check Kernel Proof Language *) | 88 (** ** An Easy-to-Check Kernel Proof Language *) |

89 | 89 |

90 (** | 90 (** |

91 %\index{de Bruijn criterion}%Scores of automated decision procedures are useful in practical theorem proving, but it is unfortunate to have to trust in the correct implementation of each procedure. Proof assistants satisfy the "de Bruijn criterion" when they produce _proof terms_ in small kernel languages, even when they use complicated and extensible procedures to seek out proofs in the first place. These core languages have feature complexity on par with what you find in proposals for formal foundations for mathematics (e.g., ZF set theory). To believe a proof, we can ignore the possibility of bugs during _search_ and just rely on a (relatively small) proof-checking kernel that we apply to the _result_ of the search. | 91 %\index{de Bruijn criterion}%Scores of automated decision procedures are useful in practical theorem proving, but it is unfortunate to have to trust in the correct implementation of each procedure. Proof assistants satisfy the "de Bruijn criterion" when they produce _proof terms_ in small kernel languages, even when they use complicated and extensible procedures to seek out proofs in the first place. These core languages have feature complexity on par with what you find in proposals for formal foundations for mathematics (e.g., ZF set theory). To believe a proof, we can ignore the possibility of bugs during _search_ and just rely on a (relatively small) proof-checking kernel that we apply to the _result_ of the search. |

92 | 92 |

93 Coq meets the de Bruijn criterion, while %\index{ACL2}%ACL2 and %\index{PVS}%PVS do not, as they employ fancy decision procedures that produce no "evidence trails" justifying their results. The HOL implementations also meet the de Bruijn criterion; for Twelf, the situation is murkier. | 93 Coq meets the de Bruijn criterion, while %\index{ACL2}%ACL2 does not, as it employs fancy decision procedures that produce no "evidence trails" justifying their results. %\index{PVS}%PVS supports _strategies_ that implement fancier proof procedures in terms of a set of primitive proof steps, where the primitive steps are less primitive than in Coq. For instance, a propositional tautology solver is included as a primitive, so it is a question of taste whether such a system meets the de Bruijn criterion. The HOL implementations meet the de Bruijn criterion more manifestly; for Twelf, the situation is murkier. |

94 *) | 94 *) |

95 | 95 |

96 (** ** Convenient Programmable Proof Automation *) | 96 (** ** Convenient Programmable Proof Automation *) |

97 | 97 |

98 (** | 98 (** |

108 (** ** Proof by Reflection *) | 108 (** ** Proof by Reflection *) |

109 | 109 |

110 (** | 110 (** |

111 %\index{reflection}\index{proof by reflection}%A surprising wealth of benefits follows from choosing a proof language that integrates a rich notion of computation. Coq includes programs and proof terms in the same syntactic class. This makes it easy to write programs that compute proofs. With rich enough dependent types, such programs are _certified decision procedures_. In such cases, these certified procedures can be put to good use _without ever running them_! Their types guarantee that, if we did bother to run them, we would receive proper "ground" proofs. | 111 %\index{reflection}\index{proof by reflection}%A surprising wealth of benefits follows from choosing a proof language that integrates a rich notion of computation. Coq includes programs and proof terms in the same syntactic class. This makes it easy to write programs that compute proofs. With rich enough dependent types, such programs are _certified decision procedures_. In such cases, these certified procedures can be put to good use _without ever running them_! Their types guarantee that, if we did bother to run them, we would receive proper "ground" proofs. |

112 | 112 |

113 The critical ingredient for this technique, many of whose instances are referred to as _proof by reflection_, is a way of inducing non-trivial computation inside of logical propositions during proof checking. Further, most of these instances require dependent types to make it possible to state the appropriate theorems. Of the proof assistants I listed, only Coq really provides this support. | 113 The critical ingredient for this technique, many of whose instances are referred to as _proof by reflection_, is a way of inducing non-trivial computation inside of logical propositions during proof checking. Further, most of these instances require dependent types to make it possible to state the appropriate theorems. Of the proof assistants I listed, only Coq really provides support for the type-level computation style of reflection, though PVS supports very similar functionality via refinement types. |

114 *) | 114 *) |

115 | 115 |

116 | 116 |

117 (** * Why Not a Different Dependently Typed Language? *) | 117 (** * Why Not a Different Dependently Typed Language? *) |

118 | 118 |