62739
|
1 |
(* Title: Doc/Corec/Corec.thy
|
|
2 |
Author: Jasmin Blanchette, Inria, LORIA, MPII
|
|
3 |
Author: Aymeric Bouzy, Ecole polytechnique
|
|
4 |
Author: Andreas Lochbihler, ETH Zuerich
|
|
5 |
Author: Andrei Popescu, Middlesex University
|
|
6 |
Author: Dmitriy Traytel, ETH Zuerich
|
|
7 |
|
|
8 |
Tutorial for nonprimitively corecursive definitions.
|
|
9 |
*)
|
|
10 |
|
|
11 |
theory Corec
|
|
12 |
imports
|
62742
|
13 |
GCD
|
62739
|
14 |
"../Datatypes/Setup"
|
|
15 |
"~~/src/HOL/Library/BNF_Corec"
|
62742
|
16 |
"~~/src/HOL/Library/FSet"
|
62739
|
17 |
begin
|
|
18 |
|
|
19 |
section \<open>Introduction
|
|
20 |
\label{sec:introduction}\<close>
|
|
21 |
|
|
22 |
text \<open>
|
|
23 |
...
|
|
24 |
\cite{isabelle-datatypes}
|
62742
|
25 |
|
|
26 |
* friend
|
|
27 |
* up to
|
|
28 |
|
62745
|
29 |
* versioning
|
|
30 |
|
62742
|
31 |
BNF
|
|
32 |
|
|
33 |
link to papers
|
62739
|
34 |
\<close>
|
|
35 |
|
|
36 |
|
|
37 |
section \<open>Introductory Examples
|
|
38 |
\label{sec:introductory-examples}\<close>
|
|
39 |
|
62742
|
40 |
text \<open>
|
|
41 |
\<close>
|
|
42 |
|
62739
|
43 |
|
|
44 |
subsection \<open>Simple Corecursion
|
|
45 |
\label{ssec:simple-corecursion}\<close>
|
|
46 |
|
62742
|
47 |
text \<open>
|
|
48 |
The case studies by Rutten~\cite{rutten05} and Hinze~\cite{hinze10} on stream
|
|
49 |
calculi serve as our starting point. Streams can be defined as follows
|
|
50 |
(cf. @{file "~~/src/HOL/Library/Stream.thy"}):
|
|
51 |
\<close>
|
|
52 |
|
|
53 |
codatatype (sset: 'a) stream =
|
|
54 |
SCons (shd: 'a) (stl: "'a stream")
|
|
55 |
for
|
|
56 |
map: smap
|
|
57 |
|
|
58 |
text \<open>
|
|
59 |
The @{command corec} command makes it possible to define functions where the
|
|
60 |
corecursive call occurs under two or more constructors:
|
|
61 |
\<close>
|
|
62 |
|
|
63 |
corec oneTwos :: "nat stream" where
|
|
64 |
"oneTwos = SCons 1 (SCons 2 oneTwos)"
|
|
65 |
|
62745
|
66 |
thm oneTwos.cong_intros
|
|
67 |
|
62742
|
68 |
text \<open>
|
|
69 |
\noindent
|
|
70 |
This is already beyond the syntactic fragment supported by \keyw{primcorec}.
|
|
71 |
|
|
72 |
The following definition of pointwise sum can be performed with either
|
|
73 |
\keyw{primcorec} or @{command corec}:
|
|
74 |
\<close>
|
|
75 |
|
|
76 |
primcorec ssum :: "('a :: plus) stream \<Rightarrow> 'a stream \<Rightarrow> 'a stream" where
|
|
77 |
"ssum xs ys = SCons (shd xs + shd ys) (ssum (stl xs) (stl ys))"
|
|
78 |
|
|
79 |
text \<open>
|
|
80 |
\noindent
|
|
81 |
Pointwise sum meets the friendliness criterion. We register it as a friend using
|
|
82 |
the @{command friend_of_corec} command. The command requires us to give a
|
|
83 |
specification of @{const ssum} where a constructor (@{const SCons}) occurs at
|
|
84 |
the outermost position on the right-hand side. Here, we can simply reuse the
|
|
85 |
\keyw{primcorec} specification above:
|
|
86 |
\<close>
|
|
87 |
|
|
88 |
friend_of_corec ssum :: "('a :: plus) stream \<Rightarrow> 'a stream \<Rightarrow> 'a stream" where
|
|
89 |
"ssum xs ys = SCons (shd xs + shd ys) (ssum (stl xs) (stl ys))"
|
|
90 |
apply (rule ssum.code)
|
|
91 |
by transfer_prover
|
|
92 |
|
|
93 |
text \<open>
|
|
94 |
\noindent
|
|
95 |
The command emits two proof goals. The first one corresponds to the equation we
|
|
96 |
specified and is trivial to discharge. The second one is a parametricity goal
|
|
97 |
and can usually be discharged using the @{text transfer_prover} proof method.
|
|
98 |
|
|
99 |
After registering @{const ssum} as a friend, we can use it in the corecursive
|
|
100 |
call context, either inside or outside the constructor guard:
|
|
101 |
\<close>
|
|
102 |
|
|
103 |
corec fibA :: "nat stream" where
|
|
104 |
"fibA = SCons 0 (ssum (SCons 1 fibA) fibA)"
|
|
105 |
|
|
106 |
text \<open>\blankline\<close>
|
|
107 |
|
|
108 |
corec fibB :: "nat stream" where
|
|
109 |
"fibB = ssum (SCons 0 (SCons 1 fibB)) (SCons 0 fibB)"
|
|
110 |
|
|
111 |
text \<open>
|
|
112 |
Using the @{text "friend"} option, we can simultaneously define a function and
|
|
113 |
register it as a friend:
|
|
114 |
\<close>
|
|
115 |
|
|
116 |
corec (friend)
|
|
117 |
sprod :: "('a :: {plus,times}) stream \<Rightarrow> 'a stream \<Rightarrow> 'a stream"
|
|
118 |
where
|
|
119 |
"sprod xs ys =
|
|
120 |
SCons (shd xs * shd ys) (ssum (sprod xs (stl ys)) (sprod (stl xs) ys))"
|
|
121 |
|
|
122 |
text \<open>\blankline\<close>
|
|
123 |
|
|
124 |
corec (friend) sexp :: "nat stream \<Rightarrow> nat stream" where
|
|
125 |
"sexp xs = SCons (2 ^^ shd xs) (sprod (stl xs) (sexp xs))"
|
|
126 |
|
|
127 |
text \<open>
|
|
128 |
\noindent
|
|
129 |
The parametricity proof goal is given to @{text transfer_prover}.
|
|
130 |
|
|
131 |
The @{const sprod} and @{const sexp} functions provide shuffle product and
|
|
132 |
exponentiation on streams. We can use them to define the stream of factorial
|
|
133 |
numbers in two different ways:
|
|
134 |
\<close>
|
|
135 |
|
|
136 |
corec factA :: "nat stream" where
|
|
137 |
"factA = (let zs = SCons 1 factA in sprod zs zs)"
|
|
138 |
|
|
139 |
corec factB :: "nat stream" where
|
|
140 |
"factB = sexp (SCons 0 factB)"
|
|
141 |
|
|
142 |
text \<open>
|
|
143 |
The arguments of friendly operations can be of complex types involving the
|
|
144 |
target codatatype. The following example defines the supremum of a finite set of
|
|
145 |
streams by primitive corecursion and registers it as friendly:
|
|
146 |
\<close>
|
|
147 |
|
|
148 |
corec (friend) sfsup :: "nat stream fset \<Rightarrow> nat stream" where
|
|
149 |
"sfsup X = SCons (Sup (fset (fimage shd X))) (sfsup (fimage stl X))"
|
|
150 |
|
|
151 |
text \<open>
|
|
152 |
\noindent
|
|
153 |
In general, the arguments may be any BNF, with the restriction that the target
|
|
154 |
codatatype (@{typ "nat stream"}) may occur only in a live position of the BNF.
|
|
155 |
For this reason, the following operation, on unbounded sets, cannot be
|
|
156 |
registered as a friend:
|
|
157 |
\<close>
|
|
158 |
|
|
159 |
corec ssup :: "nat stream set \<Rightarrow> nat stream" where
|
|
160 |
"ssup X = SCons (Sup (image shd X)) (ssup (image stl X))"
|
|
161 |
|
62739
|
162 |
|
|
163 |
subsection \<open>Nested Corecursion
|
|
164 |
\label{ssec:nested-corecursion}\<close>
|
|
165 |
|
62742
|
166 |
text \<open>
|
|
167 |
The package generally supports arbitrary codatatypes with multiple constructors
|
|
168 |
and nesting through other type constructors (BNFs). Consider the following type
|
|
169 |
of finitely branching Rose trees of potentially infinite depth:
|
|
170 |
\<close>
|
62739
|
171 |
|
62742
|
172 |
codatatype 'a tree =
|
|
173 |
Node (lab: 'a) (sub: "'a tree list")
|
|
174 |
|
|
175 |
text \<open>
|
|
176 |
We first define the pointwise sum of two trees analogously to @{const ssum}:
|
|
177 |
\<close>
|
|
178 |
|
|
179 |
corec (friend) tplus :: "('a :: plus) tree \<Rightarrow> 'a tree \<Rightarrow> 'a tree" where
|
|
180 |
"tplus t u =
|
|
181 |
Node (lab t + lab u) (map (\<lambda>(t', u'). tplus t' u') (zip (sub t) (sub u)))"
|
|
182 |
|
|
183 |
text \<open>
|
|
184 |
\noindent
|
|
185 |
Here, @{const map} is the standard map function on lists, and @{const zip}
|
|
186 |
converts two parallel lists into a list of pairs. The @{const tplus} function is
|
|
187 |
primitively corecursive. Instead of @{text "corec (friend)"}, we could also have
|
|
188 |
used \keyw{primcorec} and @{command friend_of_corec}, as we did for
|
|
189 |
@{const ssum}.
|
|
190 |
|
|
191 |
Once @{const tplus} is registered as friendly, we can use it in the corecursive
|
|
192 |
call context:
|
|
193 |
\<close>
|
|
194 |
|
|
195 |
corec (friend) ttimes :: "('a :: {plus,times}) tree \<Rightarrow> 'a tree \<Rightarrow> 'a tree" where
|
|
196 |
"ttimes t u = Node (lab t * lab u)
|
|
197 |
(map (\<lambda>(t', u'). tplus (ttimes t u') (ttimes t' u)) (zip (sub t) (sub u)))"
|
|
198 |
|
|
199 |
|
|
200 |
subsection \<open>Mixed Recursion--Corecursion
|
|
201 |
\label{ssec:mixed-recursion-corecursion}\<close>
|
|
202 |
|
|
203 |
text \<open>
|
|
204 |
It is often convenient to let a corecursive function perform some finite
|
|
205 |
computation before producing a constructor. With mixed recursion--corecursion, a
|
|
206 |
finite number of unguarded recursive calls perform this calculation before
|
|
207 |
reaching a guarded corecursive call.
|
|
208 |
|
|
209 |
Intuitively, the unguarded recursive call can be unfolded to arbitrary finite
|
|
210 |
depth, ultimately yielding a purely corecursive definition. An example is the
|
|
211 |
@{term primes} function from Di Gianantonio and Miculan
|
|
212 |
\cite{di-gianantonio-miculan-2003}:
|
|
213 |
\<close>
|
|
214 |
|
|
215 |
corecursive primes :: "nat \<Rightarrow> nat \<Rightarrow> nat stream" where
|
|
216 |
"primes m n =
|
|
217 |
(if (m = 0 \<and> n > 1) \<or> coprime m n then
|
|
218 |
SCons n (primes (m * n) (n + 1))
|
|
219 |
else
|
|
220 |
primes m (n + 1))"
|
|
221 |
apply (relation "measure (\<lambda>(m, n).
|
|
222 |
if n = 0 then 1 else if coprime m n then 0 else m - n mod m)")
|
|
223 |
apply (auto simp: mod_Suc intro: Suc_lessI)
|
|
224 |
apply (metis One_nat_def coprime_Suc_nat gcd.commute gcd_red_nat)
|
|
225 |
by (metis diff_less_mono2 lessI mod_less_divisor)
|
|
226 |
|
|
227 |
text \<open>
|
|
228 |
\noindent
|
|
229 |
The @{command corecursive} command is a variant of @{command corec} that allows
|
|
230 |
us to specify a termination argument for any unguarded self-call.
|
|
231 |
|
|
232 |
When called with @{term "m = 1"} and @{term "n = 2"}, the @{const primes}
|
|
233 |
function computes the stream of prime numbers. The unguarded call in the
|
|
234 |
@{text else} branch increments @{term n} until it is coprime to the first
|
|
235 |
argument @{term m} (i.e., the greatest common divisor of @{term m} and
|
|
236 |
@{term n} is @{term 1}).
|
|
237 |
|
|
238 |
For any positive integers @{term m} and @{term n}, the numbers @{term m} and
|
|
239 |
@{term "m * n + 1"} are coprime, yielding an upper bound on the number of times
|
|
240 |
@{term n} is increased. Hence, the function will take the @{text else} branch at
|
|
241 |
most finitely often before taking the then branch and producing one constructor.
|
|
242 |
There is a slight complication when @{term "m = 0 \<and> n > 1"}: Without the first
|
|
243 |
disjunct in the @{text "if"} condition, the function could stall. (This corner
|
|
244 |
case was overlooked in the original example \cite{di-gianantonio-miculan-2003}.)
|
|
245 |
|
|
246 |
In the following example, which defines the stream of Catalan numbers,
|
|
247 |
termination is discharged automatically using @{text lexicographic_order}:
|
|
248 |
\<close>
|
|
249 |
|
|
250 |
corec catalan :: "nat \<Rightarrow> nat stream" where
|
|
251 |
"catalan n =
|
|
252 |
(if n > 0 then ssum (catalan (n - 1)) (SCons 0 (catalan (n + 1)))
|
|
253 |
else SCons 1 (catalan 1))"
|
|
254 |
|
|
255 |
text \<open>
|
|
256 |
A more elaborate case study, revolving around the filter function on lazy lists,
|
|
257 |
is presented in @{file "~~/src/HOL/Corec_Examples/LFilter.thy"}.
|
|
258 |
\<close>
|
|
259 |
|
|
260 |
|
|
261 |
subsection \<open>Self-Friendship
|
|
262 |
\label{ssec:self-friendship}\<close>
|
|
263 |
|
|
264 |
text \<open>
|
|
265 |
Paradoxically, the package allows us to simultaneously define a function and use
|
|
266 |
it as its own friend, as in the following definition of a ``skewed product'':
|
|
267 |
\<close>
|
|
268 |
|
|
269 |
corec (friend)
|
|
270 |
sskew :: "('a :: {plus,times}) stream \<Rightarrow> 'a stream \<Rightarrow> 'a stream"
|
|
271 |
where
|
|
272 |
"sskew xs ys =
|
|
273 |
SCons (shd xs * shd ys) (sskew (sskew xs (stl ys)) (sskew (stl xs) ys))"
|
|
274 |
|
|
275 |
text \<open>
|
|
276 |
\noindent
|
|
277 |
Such definitions, with nested self-calls on the right-hand side, cannot be
|
|
278 |
separated into a @{command corec} part and a @{command friend_of_corec} part.
|
|
279 |
\<close>
|
62739
|
280 |
|
|
281 |
|
|
282 |
subsection \<open>Coinduction
|
|
283 |
\label{ssec:coinduction}\<close>
|
|
284 |
|
62742
|
285 |
text \<open>
|
|
286 |
Once a corecursive specification has been accepted, we normally want to reason
|
|
287 |
about it. The @{text codatatype} command generates a structural coinduction
|
|
288 |
principle that matches primitively corecursive functions. For nonprimitive
|
|
289 |
specifications, our package provides the more advanced proof principle of
|
|
290 |
\emph{coinduction up to congruence}---or simply \emph{coinduction up-to}.
|
|
291 |
|
|
292 |
The structural coinduction principle for @{typ "'a stream"}, called
|
|
293 |
@{thm [source] stream.coinduct}, is as follows:
|
|
294 |
%
|
|
295 |
\[@{thm stream.coinduct[no_vars]}\]
|
|
296 |
%
|
|
297 |
Coinduction allows us to prove an equality @{text "l = r"} on streams by
|
|
298 |
providing a relation @{text R} that relates @{text l} and @{text r} (first
|
|
299 |
premise) and that constitutes a bisimulation (second premise). Streams that are
|
|
300 |
related by a bisimulation cannot be distinguished by taking observations (via
|
|
301 |
the selectors @{const shd} and @{const stl}); hence they must be equal.
|
|
302 |
|
|
303 |
The coinduction up-to principle after registering @{const sskew} as friendly is
|
|
304 |
available as @{thm [source] sskew.coinduct} or
|
|
305 |
@{thm [source] stream.coinduct_upto(2)}:
|
|
306 |
%
|
|
307 |
\[@{thm sfsup.coinduct[no_vars]}\]
|
|
308 |
%
|
|
309 |
This rule is almost identical to structural coinduction, except that the
|
|
310 |
corecursive application of @{term R} is replaced by
|
|
311 |
@{term "stream.v5.congclp R"}. The @{const stream.v5.congclp} predicate is
|
|
312 |
equipped with the following introduction rules:
|
62745
|
313 |
|
|
314 |
\begin{indentblock}
|
|
315 |
\begin{description}
|
|
316 |
|
|
317 |
\item[@{thm [source] sskew.cong_base}\rm:] ~ \\
|
|
318 |
@{thm sskew.cong_base[no_vars]}
|
|
319 |
|
|
320 |
\item[@{thm [source] sskew.cong_refl}\rm:] ~ \\
|
|
321 |
@{thm sskew.cong_refl[no_vars]}
|
|
322 |
|
|
323 |
\item[@{thm [source] sskew.cong_sym}\rm:] ~ \\
|
|
324 |
@{thm sskew.cong_sym[no_vars]}
|
|
325 |
|
|
326 |
\item[@{thm [source] sskew.cong_trans}\rm:] ~ \\
|
|
327 |
@{thm sskew.cong_trans[no_vars]}
|
|
328 |
|
|
329 |
\item[@{thm [source] sskew.cong_SCons}\rm:] ~ \\
|
|
330 |
@{thm sskew.cong_SCons[no_vars]}
|
|
331 |
|
|
332 |
\item[@{thm [source] sskew.cong_ssum}\rm:] ~ \\
|
|
333 |
@{thm sskew.cong_ssum[no_vars]}
|
|
334 |
|
|
335 |
\item[@{thm [source] sskew.cong_sprod}\rm:] ~ \\
|
|
336 |
@{thm sskew.cong_sprod[no_vars]}
|
|
337 |
|
|
338 |
\item[@{thm [source] sskew.cong_sskew}\rm:] ~ \\
|
|
339 |
@{thm sskew.cong_sskew[no_vars]}
|
|
340 |
|
|
341 |
\end{description}
|
|
342 |
\end{indentblock}
|
|
343 |
%
|
|
344 |
The introduction rules are also available as
|
|
345 |
@{thm [source] sskew.cong_intros}.
|
|
346 |
|
|
347 |
Notice that there is no introduction rule corresponding to @{const sexp},
|
|
348 |
because @{const sexp} has a more restrictive result type than @{const sskew}
|
|
349 |
(@{typ "nat stream"} vs. @{typ "('a :: {plus,times}) stream"}.
|
|
350 |
|
|
351 |
Since the package maintains a set of incomparable corecursors, there is also a
|
|
352 |
set of associated coinduction principles and a set of sets of introduction
|
|
353 |
rules. A technically subtle point is to make Isabelle choose the right rules in
|
|
354 |
most situations. For this purpose, the package maintains the collection
|
|
355 |
@{thm [source] stream.coinduct_upto} of coinduction principles ordered by
|
|
356 |
increasing generality, which works well with Isabelle's philosophy of applying
|
|
357 |
the first rule that matches. For example, after registering @{const ssum} as a
|
|
358 |
friend, proving the equality @{term "l = r"} on @{typ "nat stream"} might
|
|
359 |
require coinduction principle for @{term "nat stream"}, which is up to
|
|
360 |
@{const ssum}.
|
|
361 |
|
|
362 |
The collection @{thm [source] stream.coinduct_upto} is guaranteed to be complete
|
|
363 |
and up to date with respect to the type instances of definitions considered so
|
|
364 |
far, but occasionally it may be necessary to take the union of two incomparable
|
|
365 |
coinduction principles. This can be done using the @{command coinduction_upto}
|
|
366 |
command. Consider the following definitions:
|
62742
|
367 |
\<close>
|
|
368 |
|
62745
|
369 |
codatatype (tset: 'a, 'b) tllist =
|
|
370 |
TNil (terminal : 'b)
|
|
371 |
| TCons (thd : 'a) (ttl : "('a, 'b) tllist")
|
|
372 |
for
|
|
373 |
map: tmap
|
|
374 |
rel: tllist_all2
|
|
375 |
|
|
376 |
corec (friend) square_elems :: "(nat, 'b) tllist \<Rightarrow> (nat, 'b) tllist" where
|
|
377 |
"square_elems xs =
|
|
378 |
(case xs of
|
|
379 |
TNil z \<Rightarrow> TNil z
|
|
380 |
| TCons y ys \<Rightarrow> TCons (y ^^ 2) (square_elems ys))"
|
|
381 |
|
|
382 |
corec (friend) square_terminal :: "('a, int) tllist \<Rightarrow> ('a, int) tllist" where
|
|
383 |
"square_terminal xs =
|
|
384 |
(case xs of
|
|
385 |
TNil z \<Rightarrow> TNil (z ^^ 2)
|
|
386 |
| TCons y ys \<Rightarrow> TCons y (square_terminal ys))"
|
62742
|
387 |
|
62745
|
388 |
text \<open>
|
|
389 |
At this point, @{thm [source] tllist.coinduct_upto} contains three variants of the
|
|
390 |
coinduction principles:
|
|
391 |
%
|
|
392 |
\begin{itemize}
|
|
393 |
\item @{typ "('a, int) tllist"} up to @{const TNil}, @{const TCons}, and
|
|
394 |
@{const square_terminal};
|
|
395 |
\item @{typ "(nat, 'b) tllist"} up to @{const TNil}, @{const TCons}, and
|
|
396 |
@{const square_elems};
|
|
397 |
\item @{typ "('a, 'b) tllist"} up to @{const TNil} and @{const TCons}.
|
|
398 |
\end{itemize}
|
|
399 |
%
|
|
400 |
The following variant is missing:
|
|
401 |
%
|
|
402 |
\begin{itemize}
|
|
403 |
\item @{typ "(nat, int) tllist"} up to @{const TNil}, @{const TCons},
|
|
404 |
@{const square_elems}, and @{const square_terminal}.
|
|
405 |
\end{itemize}
|
|
406 |
%
|
|
407 |
To generate it, without having to define a new function with @{command corec},
|
|
408 |
we can use the following command:
|
|
409 |
\<close>
|
62742
|
410 |
|
62745
|
411 |
coinduction_upto nat_int_tllist: "(nat, int) tllist"
|
|
412 |
|
|
413 |
text \<open>
|
|
414 |
This produces the theorems @{thm [source] nat_int_tllist.coinduct_upto} and
|
|
415 |
@{thm [source] nat_int_tllist.cong_intros} (as well as the individually named
|
|
416 |
introduction rules), and extends @{thm [source] tllist.coinduct_upto}.
|
|
417 |
\<close>
|
62742
|
418 |
|
62739
|
419 |
|
|
420 |
subsection \<open>Uniqueness Reasoning
|
|
421 |
\label{ssec:uniqueness-reasoning}\<close>
|
|
422 |
|
62742
|
423 |
text \<open>
|
62745
|
424 |
t is sometimes possible to achieve better automation by using a more specialized
|
|
425 |
proof method than coinduction. Uniqueness principles maintain a good balance
|
|
426 |
between expressiveness and automation. They exploit the property that a
|
|
427 |
corecursive specification is the unique solution to a fixpoint equation.
|
62742
|
428 |
\<close>
|
|
429 |
|
62739
|
430 |
|
|
431 |
section \<open>Command Syntax
|
|
432 |
\label{sec:command-syntax}\<close>
|
|
433 |
|
62742
|
434 |
text \<open>
|
|
435 |
...
|
|
436 |
\<close>
|
62739
|
437 |
|
62742
|
438 |
|
|
439 |
subsection \<open>\keyw{corec} and \keyw{corecursive}
|
62739
|
440 |
\label{ssec:corec-and-corecursive}\<close>
|
|
441 |
|
62742
|
442 |
text \<open>
|
|
443 |
...
|
|
444 |
\<close>
|
|
445 |
|
62739
|
446 |
|
62742
|
447 |
subsection \<open>\keyw{friend_of_corec}
|
62739
|
448 |
\label{ssec:friend-of-corec}\<close>
|
|
449 |
|
62742
|
450 |
text \<open>
|
|
451 |
...
|
|
452 |
\<close>
|
62739
|
453 |
|
62742
|
454 |
|
|
455 |
subsection \<open>\keyw{coinduction_upto}
|
62739
|
456 |
\label{ssec:coinduction-upto}\<close>
|
|
457 |
|
62742
|
458 |
text \<open>
|
|
459 |
...
|
|
460 |
\<close>
|
|
461 |
|
62739
|
462 |
|
|
463 |
section \<open>Generated Theorems
|
|
464 |
\label{sec:generated-theorems}\<close>
|
|
465 |
|
62742
|
466 |
text \<open>
|
|
467 |
...
|
|
468 |
\<close>
|
62739
|
469 |
|
62742
|
470 |
|
|
471 |
subsection \<open>\keyw{corec} and \keyw{corecursive}
|
62739
|
472 |
\label{ssec:corec-and-corecursive}\<close>
|
|
473 |
|
62742
|
474 |
text \<open>
|
|
475 |
...
|
|
476 |
\<close>
|
|
477 |
|
62739
|
478 |
|
62742
|
479 |
subsection \<open>\keyw{friend_of_corec}
|
62739
|
480 |
\label{ssec:friend-of-corec}\<close>
|
|
481 |
|
62742
|
482 |
text \<open>
|
|
483 |
...
|
|
484 |
\<close>
|
62739
|
485 |
|
62742
|
486 |
|
|
487 |
subsection \<open>\keyw{coinduction_upto}
|
62739
|
488 |
\label{ssec:coinduction-upto}\<close>
|
|
489 |
|
62742
|
490 |
text \<open>
|
|
491 |
...
|
|
492 |
\<close>
|
|
493 |
|
62739
|
494 |
|
|
495 |
section \<open>Proof Method
|
|
496 |
\label{sec:proof-method}\<close>
|
|
497 |
|
62742
|
498 |
text \<open>
|
|
499 |
...
|
|
500 |
\<close>
|
62739
|
501 |
|
62742
|
502 |
|
|
503 |
subsection \<open>\textit{corec_unique}
|
62739
|
504 |
\label{ssec:corec-unique}\<close>
|
|
505 |
|
62742
|
506 |
text \<open>
|
|
507 |
...
|
|
508 |
\<close>
|
|
509 |
|
62739
|
510 |
|
|
511 |
section \<open>Known Bugs and Limitations
|
|
512 |
\label{sec:known-bugs-and-limitations}\<close>
|
|
513 |
|
|
514 |
text \<open>
|
|
515 |
This section lists the known bugs and limitations of the corecursion package at
|
|
516 |
the time of this writing.
|
|
517 |
|
|
518 |
\begin{enumerate}
|
|
519 |
\setlength{\itemsep}{0pt}
|
|
520 |
|
|
521 |
\item
|
|
522 |
\emph{TODO.} TODO.
|
|
523 |
|
|
524 |
* no mutual types
|
|
525 |
* limitation on type of friend
|
|
526 |
* unfinished tactics
|
|
527 |
* polymorphism of corecUU_transfer
|
62742
|
528 |
* alternative views
|
62739
|
529 |
|
|
530 |
\end{enumerate}
|
|
531 |
\<close>
|
|
532 |
|
|
533 |
end
|