Mercurial > cpdt > repo
diff src/GeneralRec.v @ 514:3b21f4395178
Fix a word that was only included in LaTeX version
author | Adam Chlipala <adam@chlipala.net> |
---|---|
date | Thu, 26 Sep 2013 15:26:12 -0400 |
parents | 88688402dc82 |
children | 8f9f1e5b2fe3 |
line wrap: on
line diff
--- a/src/GeneralRec.v Thu Sep 19 17:28:32 2013 -0400 +++ b/src/GeneralRec.v Thu Sep 26 15:26:12 2013 -0400 @@ -169,7 +169,7 @@ red; intro; eapply lengthOrder_wf'; eauto. Defined. - (** Notice that we end these proofs with %\index{Vernacular commands!Defined}%[Defined], not [Qed]. Recall that [Defined] marks the theorems as %\emph{transparent}%, so that the details of their proofs may be used during program execution. Why could such details possibly matter for computation? It turns out that [Fix] satisfies the primitive recursion restriction by declaring itself as _recursive in the structure of [Acc] proofs_. This is possible because [Acc] proofs follow a predictable inductive structure. We must do work, as in the last theorem's proof, to establish that all elements of a type belong to [Acc], but the automatic unwinding of those proofs during recursion is straightforward. If we ended the proof with [Qed], the proof details would be hidden from computation, in which case the unwinding process would get stuck. + (** Notice that we end these proofs with %\index{Vernacular commands!Defined}%[Defined], not [Qed]. Recall that [Defined] marks the theorems as %\emph{%#<i>#transparent#</i>#%}%, so that the details of their proofs may be used during program execution. Why could such details possibly matter for computation? It turns out that [Fix] satisfies the primitive recursion restriction by declaring itself as _recursive in the structure of [Acc] proofs_. This is possible because [Acc] proofs follow a predictable inductive structure. We must do work, as in the last theorem's proof, to establish that all elements of a type belong to [Acc], but the automatic unwinding of those proofs during recursion is straightforward. If we ended the proof with [Qed], the proof details would be hidden from computation, in which case the unwinding process would get stuck. To justify our two recursive [mergeSort] calls, we will also need to prove that [split] respects the [lengthOrder] relation. These proofs, too, must be kept transparent, to avoid stuckness of [Fix] evaluation. We use the syntax [@foo] to reference identifier [foo] with its implicit argument behavior turned off. (The proof details below use Ltac features not introduced yet, and they are safe to skip for now.) *)