Mercurial > cpdt > repo

comparison src/Coinductive.v @ 354:dc99dffdf20a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Co-inductive non-termination monads
author Adam Chlipala <adam@chlipala.net>
date Wed, 26 Oct 2011 18:37:47 -0400
parents bb1a470c1757
children 549d604c3d16
comparison
equal deleted inserted replaced
353:3322367e955d 354:dc99dffdf20a
29 29
30 This would leave us with [bad tt] as a proof of [P]. 30 This would leave us with [bad tt] as a proof of [P].
31 31
32 There are also algorithmic considerations that make universal termination very desirable. We have seen how tactics like [reflexivity] compare terms up to equivalence under computational rules. Calls to recursive, pattern-matching functions are simplified automatically, with no need for explicit proof steps. It would be very hard to hold onto that kind of benefit if it became possible to write non-terminating programs; we would be running smack into the halting problem. 32 There are also algorithmic considerations that make universal termination very desirable. We have seen how tactics like [reflexivity] compare terms up to equivalence under computational rules. Calls to recursive, pattern-matching functions are simplified automatically, with no need for explicit proof steps. It would be very hard to hold onto that kind of benefit if it became possible to write non-terminating programs; we would be running smack into the halting problem.
33 33
34 One solution is to use types to contain the possibility of non-termination. For instance, we can create a %``%#"#non-termination monad,#"#%''% inside which we must write all of our general-recursive programs. This is a heavyweight solution, and so we would like to avoid it whenever possible. 34 One solution is to use types to contain the possibility of non-termination. For instance, we can create a %``%#"#non-termination monad,#"#%''% inside which we must write all of our general-recursive programs; several such approaches are surveyed in Chapter 7. This is a heavyweight solution, and so we would like to avoid it whenever possible.
35 35
36 Luckily, Coq has special support for a class of lazy data structures that happens to contain most examples found in Haskell. That mechanism, %\index{co-inductive types}\textit{%#<i>#co-inductive types#</i>#%}%, is the subject of this chapter. *) 36 Luckily, Coq has special support for a class of lazy data structures that happens to contain most examples found in Haskell. That mechanism, %\index{co-inductive types}\textit{%#<i>#co-inductive types#</i>#%}%, is the subject of this chapter. *)
37 37
38 38
39 (** * Computing with Infinite Data *) 39 (** * Computing with Infinite Data *)