author | blanchet |
Tue, 24 Sep 2013 17:28:23 +0200 | |
changeset 53829 | 92e71eb22ebe |
parent 53828 | 408c9a3617e3 |
child 53831 | 80423b9080cf |
permissions | -rw-r--r-- |
52792 | 1 |
(* Title: Doc/Datatypes/Datatypes.thy |
2 |
Author: Jasmin Blanchette, TU Muenchen |
|
53617 | 3 |
Author: Lorenz Panny, TU Muenchen |
4 |
Author: Andrei Popescu, TU Muenchen |
|
5 |
Author: Dmitriy Traytel, TU Muenchen |
|
52792 | 6 |
|
7 |
Tutorial for (co)datatype definitions with the new package. |
|
8 |
*) |
|
9 |
||
10 |
theory Datatypes |
|
52824 | 11 |
imports Setup |
53644 | 12 |
keywords |
53826 | 13 |
"primcorec_notyet" :: thy_decl |
52792 | 14 |
begin |
15 |
||
53644 | 16 |
(*<*) |
53822 | 17 |
(* FIXME: Temporary setup until "primcorec" and "primcorecursive" are fully implemented. *) |
53644 | 18 |
ML_command {* |
19 |
fun add_dummy_cmd _ _ lthy = lthy; |
|
20 |
||
53826 | 21 |
val _ = Outer_Syntax.local_theory @{command_spec "primcorec_notyet"} "" |
53644 | 22 |
(Parse.fixes -- Parse_Spec.where_alt_specs >> uncurry add_dummy_cmd); |
23 |
*} |
|
24 |
(*>*) |
|
25 |
||
26 |
||
52828 | 27 |
section {* Introduction |
28 |
\label{sec:introduction} *} |
|
52792 | 29 |
|
30 |
text {* |
|
53028 | 31 |
The 2013 edition of Isabelle introduced a new definitional package for freely |
32 |
generated datatypes and codatatypes. The datatype support is similar to that |
|
33 |
provided by the earlier package due to Berghofer and Wenzel |
|
34 |
\cite{Berghofer-Wenzel:1999:TPHOL}, documented in the Isar reference manual |
|
53535 | 35 |
\cite{isabelle-isar-ref}; indeed, replacing the keyword \keyw{datatype} by |
53028 | 36 |
@{command datatype_new} is usually all that is needed to port existing theories |
37 |
to use the new package. |
|
52840 | 38 |
|
52841 | 39 |
Perhaps the main advantage of the new package is that it supports recursion |
53619 | 40 |
through a large class of non-datatypes, such as finite sets: |
52792 | 41 |
*} |
42 |
||
53644 | 43 |
datatype_new 'a tree\<^sub>f\<^sub>s = Node\<^sub>f\<^sub>s (lbl\<^sub>f\<^sub>s: 'a) (sub\<^sub>f\<^sub>s: "'a tree\<^sub>f\<^sub>s fset") |
52792 | 44 |
|
45 |
text {* |
|
52794 | 46 |
\noindent |
53025 | 47 |
Another strong point is the support for local definitions: |
52792 | 48 |
*} |
49 |
||
52805 | 50 |
context linorder |
51 |
begin |
|
52841 | 52 |
datatype_new flag = Less | Eq | Greater |
52805 | 53 |
end |
52792 | 54 |
|
55 |
text {* |
|
52794 | 56 |
\noindent |
52840 | 57 |
The package also provides some convenience, notably automatically generated |
53543 | 58 |
discriminators and selectors. |
52794 | 59 |
|
53025 | 60 |
In addition to plain inductive datatypes, the new package supports coinductive |
52840 | 61 |
datatypes, or \emph{codatatypes}, which may have infinite values. For example, |
53028 | 62 |
the following command introduces the type of lazy lists, which comprises both |
63 |
finite and infinite values: |
|
52794 | 64 |
*} |
65 |
||
53623 | 66 |
(*<*) |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
67 |
locale early |
53623 | 68 |
(*>*) |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
69 |
codatatype (*<*)(in early) (*>*)'a llist = LNil | LCons 'a "'a llist" |
52794 | 70 |
|
71 |
text {* |
|
72 |
\noindent |
|
52840 | 73 |
Mixed inductive--coinductive recursion is possible via nesting. Compare the |
53028 | 74 |
following four Rose tree examples: |
52794 | 75 |
*} |
76 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
77 |
datatype_new (*<*)(in early) (*>*)'a tree\<^sub>f\<^sub>f = Node\<^sub>f\<^sub>f 'a "'a tree\<^sub>f\<^sub>f list" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
78 |
datatype_new (*<*)(in early) (*>*)'a tree\<^sub>f\<^sub>i = Node\<^sub>f\<^sub>i 'a "'a tree\<^sub>f\<^sub>i llist" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
79 |
codatatype (*<*)(in early) (*>*)'a tree\<^sub>i\<^sub>f = Node\<^sub>i\<^sub>f 'a "'a tree\<^sub>i\<^sub>f list" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
80 |
codatatype (*<*)(in early) (*>*)'a tree\<^sub>i\<^sub>i = Node\<^sub>i\<^sub>i 'a "'a tree\<^sub>i\<^sub>i llist" |
52792 | 81 |
|
52794 | 82 |
text {* |
52840 | 83 |
The first two tree types allow only finite branches, whereas the last two allow |
53028 | 84 |
branches of infinite length. Orthogonally, the nodes in the first and third |
85 |
types have finite branching, whereas those of the second and fourth may have |
|
86 |
infinitely many direct subtrees. |
|
52840 | 87 |
|
52794 | 88 |
To use the package, it is necessary to import the @{theory BNF} theory, which |
53552 | 89 |
can be precompiled into the \texttt{HOL-BNF} image. The following commands show |
52806 | 90 |
how to launch jEdit/PIDE with the image loaded and how to build the image |
91 |
without launching jEdit: |
|
52794 | 92 |
*} |
93 |
||
94 |
text {* |
|
95 |
\noindent |
|
52806 | 96 |
\ \ \ \ \texttt{isabelle jedit -l HOL-BNF} \\ |
52827 | 97 |
\noindent |
52828 | 98 |
\hbox{}\ \ \ \ \texttt{isabelle build -b HOL-BNF} |
52794 | 99 |
*} |
100 |
||
101 |
text {* |
|
52805 | 102 |
The package, like its predecessor, fully adheres to the LCF philosophy |
103 |
\cite{mgordon79}: The characteristic theorems associated with the specified |
|
104 |
(co)datatypes are derived rather than introduced axiomatically.% |
|
53543 | 105 |
\footnote{If the @{text quick_and_dirty} option is enabled, some of the |
52841 | 106 |
internal constructions and most of the internal proof obligations are skipped.} |
52805 | 107 |
The package's metatheory is described in a pair of papers |
53552 | 108 |
\cite{traytel-et-al-2012,blanchette-et-al-wit}. The central notion is that of a |
109 |
\emph{bounded natural functor} (BNF)---a well-behaved type constructor for which |
|
110 |
nested (co)recursion is supported. |
|
52792 | 111 |
|
52794 | 112 |
This tutorial is organized as follows: |
113 |
||
52805 | 114 |
\begin{itemize} |
52822 | 115 |
\setlength{\itemsep}{0pt} |
116 |
||
52805 | 117 |
\item Section \ref{sec:defining-datatypes}, ``Defining Datatypes,'' |
52822 | 118 |
describes how to specify datatypes using the @{command datatype_new} command. |
52805 | 119 |
|
53018 | 120 |
\item Section \ref{sec:defining-recursive-functions}, ``Defining Recursive |
52805 | 121 |
Functions,'' describes how to specify recursive functions using |
53535 | 122 |
@{command primrec_new}, \keyw{fun}, and \keyw{function}. |
52805 | 123 |
|
124 |
\item Section \ref{sec:defining-codatatypes}, ``Defining Codatatypes,'' |
|
53829 | 125 |
describes how to specify codatatypes using the @{command codatatype} command. |
52805 | 126 |
|
53018 | 127 |
\item Section \ref{sec:defining-corecursive-functions}, ``Defining Corecursive |
52805 | 128 |
Functions,'' describes how to specify corecursive functions using the |
53826 | 129 |
@{command primcorec} and @{command primcorecursive} commands. |
52794 | 130 |
|
53018 | 131 |
\item Section \ref{sec:registering-bounded-natural-functors}, ``Registering |
53552 | 132 |
Bounded Natural Functors,'' explains how to use the @{command bnf} command |
133 |
to register arbitrary type constructors as BNFs. |
|
52805 | 134 |
|
53552 | 135 |
\item Section |
53617 | 136 |
\ref{sec:deriving-destructors-and-theorems-for-free-constructors}, |
137 |
``Deriving Destructors and Theorems for Free Constructors,'' explains how to |
|
53552 | 138 |
use the command @{command wrap_free_constructors} to derive destructor constants |
139 |
and theorems for freely generated types, as performed internally by @{command |
|
53829 | 140 |
datatype_new} and @{command codatatype}. |
52794 | 141 |
|
53617 | 142 |
%\item Section \ref{sec:standard-ml-interface}, ``Standard ML Interface,'' |
143 |
%describes the package's programmatic interface. |
|
52794 | 144 |
|
53617 | 145 |
%\item Section \ref{sec:interoperability}, ``Interoperability,'' |
146 |
%is concerned with the packages' interaction with other Isabelle packages and |
|
147 |
%tools, such as the code generator and the counterexample generators. |
|
52805 | 148 |
|
53617 | 149 |
%\item Section \ref{sec:known-bugs-and-limitations}, ``Known Bugs and |
150 |
%Limitations,'' concludes with known open issues at the time of writing. |
|
52805 | 151 |
\end{itemize} |
52822 | 152 |
|
153 |
||
154 |
\newbox\boxA |
|
155 |
\setbox\boxA=\hbox{\texttt{nospam}} |
|
156 |
||
157 |
\newcommand\authoremaili{\texttt{blan{\color{white}nospam}\kern-\wd\boxA{}chette@\allowbreak |
|
158 |
in.\allowbreak tum.\allowbreak de}} |
|
53028 | 159 |
\newcommand\authoremailii{\texttt{lore{\color{white}nospam}\kern-\wd\boxA{}nz.panny@\allowbreak |
160 |
\allowbreak tum.\allowbreak de}} |
|
161 |
\newcommand\authoremailiii{\texttt{pope{\color{white}nospam}\kern-\wd\boxA{}scua@\allowbreak |
|
52822 | 162 |
in.\allowbreak tum.\allowbreak de}} |
53028 | 163 |
\newcommand\authoremailiv{\texttt{tray{\color{white}nospam}\kern-\wd\boxA{}tel@\allowbreak |
52822 | 164 |
in.\allowbreak tum.\allowbreak de}} |
165 |
||
53028 | 166 |
The commands @{command datatype_new} and @{command primrec_new} are expected to |
53535 | 167 |
displace \keyw{datatype} and \keyw{primrec} in a future release. Authors of new |
168 |
theories are encouraged to use the new commands, and maintainers of older |
|
53028 | 169 |
theories may want to consider upgrading. |
52841 | 170 |
|
171 |
Comments and bug reports concerning either the tool or this tutorial should be |
|
53028 | 172 |
directed to the authors at \authoremaili, \authoremailii, \authoremailiii, |
173 |
and \authoremailiv. |
|
52822 | 174 |
|
175 |
\begin{framed} |
|
176 |
\noindent |
|
53646 | 177 |
\textbf{Warning:}\enskip This tutorial and the package it describes are under |
178 |
construction. Please apologise for their appearance. Should you have suggestions |
|
179 |
or comments regarding either, please let the authors know. |
|
52822 | 180 |
\end{framed} |
52794 | 181 |
*} |
182 |
||
53491 | 183 |
|
52827 | 184 |
section {* Defining Datatypes |
52805 | 185 |
\label{sec:defining-datatypes} *} |
186 |
||
187 |
text {* |
|
53646 | 188 |
Datatypes can be specified using the @{command datatype_new} command. |
52805 | 189 |
*} |
52792 | 190 |
|
52824 | 191 |
|
53617 | 192 |
subsection {* Introductory Examples |
193 |
\label{ssec:datatype-introductory-examples} *} |
|
52794 | 194 |
|
53646 | 195 |
text {* |
196 |
Datatypes are illustrated through concrete examples featuring different flavors |
|
197 |
of recursion. More examples can be found in the directory |
|
198 |
\verb|~~/src/HOL/BNF/Examples|. |
|
199 |
*} |
|
53621 | 200 |
|
201 |
subsubsection {* Nonrecursive Types |
|
202 |
\label{sssec:datatype-nonrecursive-types} *} |
|
52794 | 203 |
|
52805 | 204 |
text {* |
53028 | 205 |
Datatypes are introduced by specifying the desired names and argument types for |
53491 | 206 |
their constructors. \emph{Enumeration} types are the simplest form of datatype. |
53028 | 207 |
All their constructors are nullary: |
52805 | 208 |
*} |
209 |
||
52828 | 210 |
datatype_new trool = Truue | Faalse | Perhaaps |
52805 | 211 |
|
212 |
text {* |
|
53028 | 213 |
\noindent |
53491 | 214 |
Here, @{const Truue}, @{const Faalse}, and @{const Perhaaps} have the type @{typ trool}. |
53028 | 215 |
|
216 |
Polymorphic types are possible, such as the following option type, modeled after |
|
217 |
its homologue from the @{theory Option} theory: |
|
52805 | 218 |
*} |
219 |
||
53025 | 220 |
(*<*) |
221 |
hide_const None Some |
|
222 |
(*>*) |
|
223 |
datatype_new 'a option = None | Some 'a |
|
52805 | 224 |
|
225 |
text {* |
|
53028 | 226 |
\noindent |
53491 | 227 |
The constructors are @{text "None :: 'a option"} and |
228 |
@{text "Some :: 'a \<Rightarrow> 'a option"}. |
|
53028 | 229 |
|
230 |
The next example has three type parameters: |
|
52805 | 231 |
*} |
232 |
||
233 |
datatype_new ('a, 'b, 'c) triple = Triple 'a 'b 'c |
|
234 |
||
53028 | 235 |
text {* |
236 |
\noindent |
|
237 |
The constructor is |
|
53491 | 238 |
@{text "Triple :: 'a \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> ('a, 'b, 'c) triple"}. |
53028 | 239 |
Unlike in Standard ML, curried constructors are supported. The uncurried variant |
240 |
is also possible: |
|
241 |
*} |
|
242 |
||
243 |
datatype_new ('a, 'b, 'c) triple\<^sub>u = Triple\<^sub>u "'a * 'b * 'c" |
|
244 |
||
52824 | 245 |
|
53621 | 246 |
subsubsection {* Simple Recursion |
247 |
\label{sssec:datatype-simple-recursion} *} |
|
52794 | 248 |
|
52805 | 249 |
text {* |
53491 | 250 |
Natural numbers are the simplest example of a recursive type: |
52805 | 251 |
*} |
252 |
||
53332 | 253 |
datatype_new nat = Zero | Suc nat |
52805 | 254 |
|
255 |
text {* |
|
53491 | 256 |
\noindent |
257 |
Lists were shown in the introduction. Terminated lists are a variant: |
|
52805 | 258 |
*} |
259 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
260 |
datatype_new (*<*)(in early) (*>*)('a, 'b) tlist = TNil 'b | TCons 'a "('a, 'b) tlist" |
52805 | 261 |
|
262 |
text {* |
|
53491 | 263 |
\noindent |
53552 | 264 |
Occurrences of nonatomic types on the right-hand side of the equal sign must be |
265 |
enclosed in double quotes, as is customary in Isabelle. |
|
52805 | 266 |
*} |
267 |
||
52824 | 268 |
|
53621 | 269 |
subsubsection {* Mutual Recursion |
270 |
\label{sssec:datatype-mutual-recursion} *} |
|
52794 | 271 |
|
52805 | 272 |
text {* |
53552 | 273 |
\emph{Mutually recursive} types are introduced simultaneously and may refer to |
274 |
each other. The example below introduces a pair of types for even and odd |
|
275 |
natural numbers: |
|
52805 | 276 |
*} |
277 |
||
53623 | 278 |
datatype_new even_nat = Even_Zero | Even_Suc odd_nat |
279 |
and odd_nat = Odd_Suc even_nat |
|
52805 | 280 |
|
281 |
text {* |
|
53491 | 282 |
\noindent |
283 |
Arithmetic expressions are defined via terms, terms via factors, and factors via |
|
284 |
expressions: |
|
52805 | 285 |
*} |
286 |
||
52841 | 287 |
datatype_new ('a, 'b) exp = |
288 |
Term "('a, 'b) trm" | Sum "('a, 'b) trm" "('a, 'b) exp" |
|
52805 | 289 |
and ('a, 'b) trm = |
52841 | 290 |
Factor "('a, 'b) fct" | Prod "('a, 'b) fct" "('a, 'b) trm" |
291 |
and ('a, 'b) fct = |
|
292 |
Const 'a | Var 'b | Expr "('a, 'b) exp" |
|
52805 | 293 |
|
52824 | 294 |
|
53621 | 295 |
subsubsection {* Nested Recursion |
296 |
\label{sssec:datatype-nested-recursion} *} |
|
52794 | 297 |
|
52805 | 298 |
text {* |
53491 | 299 |
\emph{Nested recursion} occurs when recursive occurrences of a type appear under |
300 |
a type constructor. The introduction showed some examples of trees with nesting |
|
53675 | 301 |
through lists. A more complex example, that reuses our @{type option} type, |
53491 | 302 |
follows: |
52805 | 303 |
*} |
304 |
||
52843 | 305 |
datatype_new 'a btree = |
53025 | 306 |
BNode 'a "'a btree option" "'a btree option" |
52805 | 307 |
|
308 |
text {* |
|
53491 | 309 |
\noindent |
310 |
Not all nestings are admissible. For example, this command will fail: |
|
52805 | 311 |
*} |
312 |
||
53491 | 313 |
datatype_new 'a wrong = Wrong (*<*)'a |
53542 | 314 |
typ (*>*)"'a wrong \<Rightarrow> 'a" |
52806 | 315 |
|
316 |
text {* |
|
53491 | 317 |
\noindent |
318 |
The issue is that the function arrow @{text "\<Rightarrow>"} allows recursion |
|
319 |
only through its right-hand side. This issue is inherited by polymorphic |
|
320 |
datatypes defined in terms of~@{text "\<Rightarrow>"}: |
|
321 |
*} |
|
322 |
||
323 |
datatype_new ('a, 'b) fn = Fn "'a \<Rightarrow> 'b" |
|
324 |
datatype_new 'a also_wrong = Also_Wrong (*<*)'a |
|
53542 | 325 |
typ (*>*)"('a also_wrong, 'a) fn" |
53491 | 326 |
|
327 |
text {* |
|
328 |
\noindent |
|
53621 | 329 |
This is legal: |
330 |
*} |
|
331 |
||
332 |
datatype_new 'a ftree = FTLeaf 'a | FTNode "'a \<Rightarrow> 'a ftree" |
|
333 |
||
334 |
text {* |
|
335 |
\noindent |
|
53491 | 336 |
In general, type constructors @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
337 |
allow recursion on a subset of their type arguments @{text 'a\<^sub>1}, \ldots, |
|
338 |
@{text 'a\<^sub>m}. These type arguments are called \emph{live}; the remaining |
|
339 |
type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and |
|
340 |
@{typ "('a, 'b) fn"}, the type variable @{typ 'a} is dead and @{typ 'b} is live. |
|
53552 | 341 |
|
53647 | 342 |
Type constructors must be registered as BNFs to have live arguments. This is |
343 |
done automatically for datatypes and codatatypes introduced by the @{command |
|
53829 | 344 |
datatype_new} and @{command codatatype} commands. |
53552 | 345 |
Section~\ref{sec:registering-bounded-natural-functors} explains how to register |
346 |
arbitrary type constructors as BNFs. |
|
52806 | 347 |
*} |
348 |
||
349 |
||
53621 | 350 |
subsubsection {* Custom Names and Syntaxes |
351 |
\label{sssec:datatype-custom-names-and-syntaxes} *} |
|
52805 | 352 |
|
353 |
text {* |
|
53491 | 354 |
The @{command datatype_new} command introduces various constants in addition to |
53617 | 355 |
the constructors. With each datatype are associated set functions, a map |
356 |
function, a relator, discriminators, and selectors, all of which can be given |
|
357 |
custom names. In the example below, the traditional names |
|
358 |
@{text set}, @{text map}, @{text list_all2}, @{text null}, @{text hd}, and |
|
359 |
@{text tl} override the default names @{text list_set}, @{text list_map}, @{text |
|
360 |
list_rel}, @{text is_Nil}, @{text un_Cons1}, and @{text un_Cons2}: |
|
52822 | 361 |
*} |
362 |
||
52841 | 363 |
(*<*) |
364 |
no_translations |
|
365 |
"[x, xs]" == "x # [xs]" |
|
366 |
"[x]" == "x # []" |
|
367 |
||
368 |
no_notation |
|
369 |
Nil ("[]") and |
|
370 |
Cons (infixr "#" 65) |
|
371 |
||
53543 | 372 |
hide_type list |
53544 | 373 |
hide_const Nil Cons hd tl set map list_all2 list_case list_rec |
53025 | 374 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
375 |
context early begin |
52841 | 376 |
(*>*) |
53025 | 377 |
datatype_new (set: 'a) list (map: map rel: list_all2) = |
52822 | 378 |
null: Nil (defaults tl: Nil) |
53025 | 379 |
| Cons (hd: 'a) (tl: "'a list") |
52822 | 380 |
|
381 |
text {* |
|
382 |
\noindent |
|
383 |
The command introduces a discriminator @{const null} and a pair of selectors |
|
384 |
@{const hd} and @{const tl} characterized as follows: |
|
385 |
% |
|
53025 | 386 |
\[@{thm list.collapse(1)[of xs, no_vars]} |
387 |
\qquad @{thm list.collapse(2)[of xs, no_vars]}\] |
|
52822 | 388 |
% |
389 |
For two-constructor datatypes, a single discriminator constant suffices. The |
|
53491 | 390 |
discriminator associated with @{const Cons} is simply |
391 |
@{term "\<lambda>xs. \<not> null xs"}. |
|
52822 | 392 |
|
53553 | 393 |
The @{text defaults} clause following the @{const Nil} constructor specifies a |
394 |
default value for selectors associated with other constructors. Here, it is used |
|
395 |
to ensure that the tail of the empty list is itself (instead of being left |
|
53535 | 396 |
unspecified). |
52822 | 397 |
|
53617 | 398 |
Because @{const Nil} is nullary, it is also possible to use |
53491 | 399 |
@{term "\<lambda>xs. xs = Nil"} as a discriminator. This is specified by |
53534 | 400 |
entering ``@{text "="}'' instead of the identifier @{const null}. Although this |
53535 | 401 |
may look appealing, the mixture of constructors and selectors in the |
53534 | 402 |
characteristic theorems can lead Isabelle's automation to switch between the |
403 |
constructor and the destructor view in surprising ways. |
|
52822 | 404 |
|
53491 | 405 |
The usual mixfix syntaxes are available for both types and constructors. For |
406 |
example: |
|
52805 | 407 |
*} |
52794 | 408 |
|
53025 | 409 |
(*<*) |
410 |
end |
|
411 |
(*>*) |
|
53552 | 412 |
datatype_new ('a, 'b) prod (infixr "*" 20) = Pair 'a 'b |
413 |
||
414 |
text {* \blankline *} |
|
52822 | 415 |
|
52841 | 416 |
datatype_new (set: 'a) list (map: map rel: list_all2) = |
52822 | 417 |
null: Nil ("[]") |
52841 | 418 |
| Cons (hd: 'a) (tl: "'a list") (infixr "#" 65) |
419 |
||
420 |
text {* |
|
53535 | 421 |
\noindent |
53025 | 422 |
Incidentally, this is how the traditional syntaxes can be set up: |
52841 | 423 |
*} |
424 |
||
425 |
syntax "_list" :: "args \<Rightarrow> 'a list" ("[(_)]") |
|
426 |
||
53552 | 427 |
text {* \blankline *} |
428 |
||
52841 | 429 |
translations |
430 |
"[x, xs]" == "x # [xs]" |
|
431 |
"[x]" == "x # []" |
|
52822 | 432 |
|
52824 | 433 |
|
53617 | 434 |
subsection {* Command Syntax |
435 |
\label{ssec:datatype-command-syntax} *} |
|
436 |
||
437 |
||
53621 | 438 |
subsubsection {* \keyw{datatype\_new} |
439 |
\label{sssec:datatype-new} *} |
|
52794 | 440 |
|
52822 | 441 |
text {* |
53829 | 442 |
\begin{matharray}{rcl} |
443 |
@{command_def "datatype_new"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
444 |
\end{matharray} |
|
52822 | 445 |
|
52824 | 446 |
@{rail " |
53829 | 447 |
@@{command datatype_new} target? @{syntax dt_options}? \\ |
52824 | 448 |
(@{syntax dt_name} '=' (@{syntax ctor} + '|') + @'and') |
52828 | 449 |
; |
53623 | 450 |
@{syntax_def dt_options}: '(' (('no_discs_sels' | 'rep_compat') + ',') ')' |
52824 | 451 |
"} |
452 |
||
53534 | 453 |
The syntactic quantity \synt{target} can be used to specify a local |
454 |
context---e.g., @{text "(in linorder)"}. It is documented in the Isar reference |
|
455 |
manual \cite{isabelle-isar-ref}. |
|
456 |
% |
|
457 |
The optional target is optionally followed by datatype-specific options: |
|
52822 | 458 |
|
52824 | 459 |
\begin{itemize} |
460 |
\setlength{\itemsep}{0pt} |
|
461 |
||
462 |
\item |
|
53623 | 463 |
The @{text "no_discs_sels"} option indicates that no discriminators or selectors |
53543 | 464 |
should be generated. |
52822 | 465 |
|
52824 | 466 |
\item |
53644 | 467 |
The @{text "rep_compat"} option indicates that the generated names should |
468 |
contain optional (and normally not displayed) ``@{text "new."}'' components to |
|
469 |
prevent clashes with a later call to \keyw{rep\_datatype}. See |
|
52824 | 470 |
Section~\ref{ssec:datatype-compatibility-issues} for details. |
471 |
\end{itemize} |
|
52822 | 472 |
|
52827 | 473 |
The left-hand sides of the datatype equations specify the name of the type to |
53534 | 474 |
define, its type parameters, and additional information: |
52822 | 475 |
|
52824 | 476 |
@{rail " |
53534 | 477 |
@{syntax_def dt_name}: @{syntax tyargs}? name @{syntax map_rel}? mixfix? |
52824 | 478 |
; |
53534 | 479 |
@{syntax_def tyargs}: typefree | '(' ((name ':')? typefree + ',') ')' |
52824 | 480 |
; |
53534 | 481 |
@{syntax_def map_rel}: '(' ((('map' | 'rel') ':' name) +) ')' |
52824 | 482 |
"} |
52822 | 483 |
|
52827 | 484 |
\noindent |
53534 | 485 |
The syntactic quantity \synt{name} denotes an identifier, \synt{typefree} |
486 |
denotes fixed type variable (@{typ 'a}, @{typ 'b}, \ldots), and \synt{mixfix} |
|
487 |
denotes the usual parenthesized mixfix notation. They are documented in the Isar |
|
488 |
reference manual \cite{isabelle-isar-ref}. |
|
52822 | 489 |
|
52827 | 490 |
The optional names preceding the type variables allow to override the default |
491 |
names of the set functions (@{text t_set1}, \ldots, @{text t_setM}). |
|
53647 | 492 |
Inside a mutually recursive specification, all defined datatypes must |
493 |
mention exactly the same type variables in the same order. |
|
52822 | 494 |
|
52824 | 495 |
@{rail " |
53534 | 496 |
@{syntax_def ctor}: (name ':')? name (@{syntax ctor_arg} * ) \\ |
497 |
@{syntax dt_sel_defaults}? mixfix? |
|
52824 | 498 |
"} |
499 |
||
53535 | 500 |
\medskip |
501 |
||
52827 | 502 |
\noindent |
503 |
The main constituents of a constructor specification is the name of the |
|
504 |
constructor and the list of its argument types. An optional discriminator name |
|
53554 | 505 |
can be supplied at the front to override the default name |
506 |
(@{text t.is_C\<^sub>j}). |
|
52822 | 507 |
|
52824 | 508 |
@{rail " |
53534 | 509 |
@{syntax_def ctor_arg}: type | '(' name ':' type ')' |
52827 | 510 |
"} |
511 |
||
53535 | 512 |
\medskip |
513 |
||
52827 | 514 |
\noindent |
515 |
In addition to the type of a constructor argument, it is possible to specify a |
|
516 |
name for the corresponding selector to override the default name |
|
53554 | 517 |
(@{text un_C\<^sub>ji}). The same selector names can be reused for several |
518 |
constructors as long as they share the same type. |
|
52827 | 519 |
|
520 |
@{rail " |
|
53621 | 521 |
@{syntax_def dt_sel_defaults}: '(' 'defaults' (name ':' term +) ')' |
52824 | 522 |
"} |
52827 | 523 |
|
524 |
\noindent |
|
525 |
Given a constructor |
|
526 |
@{text "C \<Colon> \<sigma>\<^sub>1 \<Rightarrow> \<dots> \<Rightarrow> \<sigma>\<^sub>p \<Rightarrow> \<sigma>"}, |
|
527 |
default values can be specified for any selector |
|
528 |
@{text "un_D \<Colon> \<sigma> \<Rightarrow> \<tau>"} |
|
53535 | 529 |
associated with other constructors. The specified default value must be of type |
52828 | 530 |
@{text "\<sigma>\<^sub>1 \<Rightarrow> \<dots> \<Rightarrow> \<sigma>\<^sub>p \<Rightarrow> \<tau>"} |
53535 | 531 |
(i.e., it may depends on @{text C}'s arguments). |
52822 | 532 |
*} |
533 |
||
53617 | 534 |
|
53621 | 535 |
subsubsection {* \keyw{datatype\_new\_compat} |
536 |
\label{sssec:datatype-new-compat} *} |
|
53617 | 537 |
|
538 |
text {* |
|
53829 | 539 |
\begin{matharray}{rcl} |
540 |
@{command_def "datatype_new_compat"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
541 |
\end{matharray} |
|
542 |
||
543 |
@{rail " |
|
544 |
@@{command datatype_new_compat} names |
|
545 |
"} |
|
546 |
||
547 |
\noindent |
|
53621 | 548 |
The old datatype package provides some functionality that is not yet replicated |
549 |
in the new package: |
|
550 |
||
551 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
552 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
553 |
|
53621 | 554 |
\item It is integrated with \keyw{fun} and \keyw{function} |
555 |
\cite{isabelle-function}, Nitpick \cite{isabelle-nitpick}, Quickcheck, |
|
556 |
and other packages. |
|
557 |
||
558 |
\item It is extended by various add-ons, notably to produce instances of the |
|
559 |
@{const size} function. |
|
560 |
\end{itemize} |
|
561 |
||
562 |
\noindent |
|
563 |
New-style datatypes can in most case be registered as old-style datatypes using |
|
53829 | 564 |
@{command datatype_new_compat}. The \textit{names} argument is a space-separated |
565 |
list of type names that are mutually recursive. For example: |
|
53621 | 566 |
*} |
567 |
||
53623 | 568 |
datatype_new_compat even_nat odd_nat |
53621 | 569 |
|
570 |
text {* \blankline *} |
|
571 |
||
53623 | 572 |
thm even_nat_odd_nat.size |
53621 | 573 |
|
574 |
text {* \blankline *} |
|
575 |
||
53623 | 576 |
ML {* Datatype_Data.get_info @{theory} @{type_name even_nat} *} |
53621 | 577 |
|
578 |
text {* |
|
53748 | 579 |
A few remarks concern nested recursive datatypes only: |
580 |
||
581 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
582 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
583 |
|
53748 | 584 |
\item The old-style, nested-as-mutual induction rule, iterator theorems, and |
585 |
recursor theorems are generated under their usual names but with ``@{text |
|
586 |
"compat_"}'' prefixed (e.g., @{text compat_tree.induct}). |
|
587 |
||
588 |
\item All types through which recursion takes place must be new-style datatypes |
|
589 |
or the function type. In principle, it should be possible to support old-style |
|
590 |
datatypes as well, but the command does not support this yet (and there is |
|
591 |
currently no way to register old-style datatypes as new-style datatypes). |
|
592 |
\end{itemize} |
|
593 |
||
594 |
An alternative to @{command datatype_new_compat} is to use the old package's |
|
595 |
\keyw{rep\_datatype} command. The associated proof obligations must then be |
|
596 |
discharged manually. |
|
53617 | 597 |
*} |
598 |
||
599 |
||
600 |
subsection {* Generated Constants |
|
601 |
\label{ssec:datatype-generated-constants} *} |
|
602 |
||
603 |
text {* |
|
53623 | 604 |
Given a datatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
53617 | 605 |
with $m > 0$ live type variables and $n$ constructors |
606 |
@{text "t.C\<^sub>1"}, \ldots, @{text "t.C\<^sub>n"}, the |
|
607 |
following auxiliary constants are introduced: |
|
608 |
||
609 |
\begin{itemize} |
|
610 |
\setlength{\itemsep}{0pt} |
|
611 |
||
612 |
\item \relax{Case combinator}: @{text t_case} (rendered using the familiar |
|
613 |
@{text case}--@{text of} syntax) |
|
614 |
||
615 |
\item \relax{Discriminators}: @{text "t.is_C\<^sub>1"}, \ldots, |
|
616 |
@{text "t.is_C\<^sub>n"} |
|
617 |
||
618 |
\item \relax{Selectors}: |
|
619 |
@{text t.un_C\<^sub>11}$, \ldots, @{text t.un_C\<^sub>1k\<^sub>1}, \\ |
|
620 |
\phantom{\relax{Selectors:}} \quad\vdots \\ |
|
621 |
\phantom{\relax{Selectors:}} @{text t.un_C\<^sub>n1}$, \ldots, @{text t.un_C\<^sub>nk\<^sub>n}. |
|
622 |
||
623 |
\item \relax{Set functions} (or \relax{natural transformations}): |
|
624 |
@{text t_set1}, \ldots, @{text t_setm} |
|
625 |
||
626 |
\item \relax{Map function} (or \relax{functorial action}): @{text t_map} |
|
627 |
||
628 |
\item \relax{Relator}: @{text t_rel} |
|
629 |
||
630 |
\item \relax{Iterator}: @{text t_fold} |
|
631 |
||
632 |
\item \relax{Recursor}: @{text t_rec} |
|
633 |
||
634 |
\end{itemize} |
|
635 |
||
636 |
\noindent |
|
637 |
The case combinator, discriminators, and selectors are collectively called |
|
638 |
\emph{destructors}. The prefix ``@{text "t."}'' is an optional component of the |
|
639 |
name and is normally hidden. |
|
640 |
*} |
|
641 |
||
642 |
||
52840 | 643 |
subsection {* Generated Theorems |
644 |
\label{ssec:datatype-generated-theorems} *} |
|
52828 | 645 |
|
646 |
text {* |
|
53544 | 647 |
The characteristic theorems generated by @{command datatype_new} are grouped in |
53623 | 648 |
three broad categories: |
53535 | 649 |
|
53543 | 650 |
\begin{itemize} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
651 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
652 |
|
53543 | 653 |
\item The \emph{free constructor theorems} are properties about the constructors |
654 |
and destructors that can be derived for any freely generated type. Internally, |
|
53542 | 655 |
the derivation is performed by @{command wrap_free_constructors}. |
53535 | 656 |
|
53552 | 657 |
\item The \emph{functorial theorems} are properties of datatypes related to |
658 |
their BNF nature. |
|
659 |
||
660 |
\item The \emph{inductive theorems} are properties of datatypes related to |
|
53544 | 661 |
their inductive nature. |
53552 | 662 |
|
53543 | 663 |
\end{itemize} |
53535 | 664 |
|
665 |
\noindent |
|
53542 | 666 |
The full list of named theorems can be obtained as usual by entering the |
53543 | 667 |
command \keyw{print\_theorems} immediately after the datatype definition. |
53542 | 668 |
This list normally excludes low-level theorems that reveal internal |
53552 | 669 |
constructions. To make these accessible, add the line |
53542 | 670 |
*} |
53535 | 671 |
|
53542 | 672 |
declare [[bnf_note_all]] |
673 |
(*<*) |
|
674 |
declare [[bnf_note_all = false]] |
|
675 |
(*>*) |
|
53535 | 676 |
|
53552 | 677 |
text {* |
678 |
\noindent |
|
679 |
to the top of the theory file. |
|
680 |
*} |
|
53535 | 681 |
|
53621 | 682 |
subsubsection {* Free Constructor Theorems |
683 |
\label{sssec:free-constructor-theorems} *} |
|
53535 | 684 |
|
53543 | 685 |
(*<*) |
686 |
consts is_Cons :: 'a |
|
687 |
(*>*) |
|
688 |
||
53535 | 689 |
text {* |
53543 | 690 |
The first subgroup of properties are concerned with the constructors. |
691 |
They are listed below for @{typ "'a list"}: |
|
692 |
||
53552 | 693 |
\begin{indentblock} |
53543 | 694 |
\begin{description} |
53544 | 695 |
|
53642 | 696 |
\item[@{text "t."}\hthm{inject} @{text "[iff, induct_simp]"}\rm:] ~ \\ |
53544 | 697 |
@{thm list.inject[no_vars]} |
698 |
||
53642 | 699 |
\item[@{text "t."}\hthm{distinct} @{text "[simp, induct_simp]"}\rm:] ~ \\ |
53543 | 700 |
@{thm list.distinct(1)[no_vars]} \\ |
701 |
@{thm list.distinct(2)[no_vars]} |
|
702 |
||
53642 | 703 |
\item[@{text "t."}\hthm{exhaust} @{text "[cases t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 704 |
@{thm list.exhaust[no_vars]} |
705 |
||
53642 | 706 |
\item[@{text "t."}\hthm{nchotomy}\rm:] ~ \\ |
53543 | 707 |
@{thm list.nchotomy[no_vars]} |
708 |
||
709 |
\end{description} |
|
53552 | 710 |
\end{indentblock} |
53543 | 711 |
|
712 |
\noindent |
|
53621 | 713 |
In addition, these nameless theorems are registered as safe elimination rules: |
714 |
||
715 |
\begin{indentblock} |
|
716 |
\begin{description} |
|
717 |
||
53642 | 718 |
\item[@{text "t."}\hthm{list.distinct {\upshape[}THEN notE}@{text ", elim!"}\hthm{\upshape]}\rm:] ~ \\ |
53621 | 719 |
@{thm list.distinct(1)[THEN notE, elim!, no_vars]} \\ |
720 |
@{thm list.distinct(2)[THEN notE, elim!, no_vars]} |
|
721 |
||
722 |
\end{description} |
|
723 |
\end{indentblock} |
|
724 |
||
725 |
\noindent |
|
53543 | 726 |
The next subgroup is concerned with the case combinator: |
727 |
||
53552 | 728 |
\begin{indentblock} |
53543 | 729 |
\begin{description} |
53544 | 730 |
|
53798 | 731 |
\item[@{text "t."}\hthm{case} @{text "[simp, code]"}\rm:] ~ \\ |
53543 | 732 |
@{thm list.case(1)[no_vars]} \\ |
733 |
@{thm list.case(2)[no_vars]} |
|
734 |
||
53642 | 735 |
\item[@{text "t."}\hthm{case\_cong}\rm:] ~ \\ |
53543 | 736 |
@{thm list.case_cong[no_vars]} |
737 |
||
53642 | 738 |
\item[@{text "t."}\hthm{weak\_case\_cong} @{text "[cong]"}\rm:] ~ \\ |
53543 | 739 |
@{thm list.weak_case_cong[no_vars]} |
740 |
||
53642 | 741 |
\item[@{text "t."}\hthm{split}\rm:] ~ \\ |
53543 | 742 |
@{thm list.split[no_vars]} |
743 |
||
53642 | 744 |
\item[@{text "t."}\hthm{split\_asm}\rm:] ~ \\ |
53543 | 745 |
@{thm list.split_asm[no_vars]} |
746 |
||
53544 | 747 |
\item[@{text "t."}\hthm{splits} = @{text "split split_asm"}] |
53543 | 748 |
|
749 |
\end{description} |
|
53552 | 750 |
\end{indentblock} |
53543 | 751 |
|
752 |
\noindent |
|
753 |
The third and last subgroup revolves around discriminators and selectors: |
|
754 |
||
53552 | 755 |
\begin{indentblock} |
53543 | 756 |
\begin{description} |
53544 | 757 |
|
53694 | 758 |
\item[@{text "t."}\hthm{disc} @{text "[simp]"}\rm:] ~ \\ |
759 |
@{thm list.disc(1)[no_vars]} \\ |
|
760 |
@{thm list.disc(2)[no_vars]} |
|
761 |
||
53703 | 762 |
\item[@{text "t."}\hthm{discI}\rm:] ~ \\ |
763 |
@{thm list.discI(1)[no_vars]} \\ |
|
764 |
@{thm list.discI(2)[no_vars]} |
|
765 |
||
53805 | 766 |
\item[@{text "t."}\hthm{sel} @{text "[simp, code]"}\rm:] ~ \\ |
53694 | 767 |
@{thm list.sel(1)[no_vars]} \\ |
768 |
@{thm list.sel(2)[no_vars]} |
|
53543 | 769 |
|
53642 | 770 |
\item[@{text "t."}\hthm{collapse} @{text "[simp]"}\rm:] ~ \\ |
53543 | 771 |
@{thm list.collapse(1)[no_vars]} \\ |
772 |
@{thm list.collapse(2)[no_vars]} |
|
773 |
||
53642 | 774 |
\item[@{text "t."}\hthm{disc\_exclude}\rm:] ~ \\ |
53543 | 775 |
These properties are missing for @{typ "'a list"} because there is only one |
776 |
proper discriminator. Had the datatype been introduced with a second |
|
53544 | 777 |
discriminator called @{const is_Cons}, they would have read thusly: \\[\jot] |
53543 | 778 |
@{prop "null list \<Longrightarrow> \<not> is_Cons list"} \\ |
779 |
@{prop "is_Cons list \<Longrightarrow> \<not> null list"} |
|
780 |
||
53642 | 781 |
\item[@{text "t."}\hthm{disc\_exhaust} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 782 |
@{thm list.disc_exhaust[no_vars]} |
783 |
||
53642 | 784 |
\item[@{text "t."}\hthm{expand}\rm:] ~ \\ |
53543 | 785 |
@{thm list.expand[no_vars]} |
786 |
||
53642 | 787 |
\item[@{text "t."}\hthm{case\_conv}\rm:] ~ \\ |
53543 | 788 |
@{thm list.case_conv[no_vars]} |
789 |
||
790 |
\end{description} |
|
53552 | 791 |
\end{indentblock} |
792 |
*} |
|
793 |
||
794 |
||
53621 | 795 |
subsubsection {* Functorial Theorems |
796 |
\label{sssec:functorial-theorems} *} |
|
53552 | 797 |
|
798 |
text {* |
|
53623 | 799 |
The BNF-related theorem are as follows: |
53552 | 800 |
|
801 |
\begin{indentblock} |
|
802 |
\begin{description} |
|
803 |
||
53798 | 804 |
\item[@{text "t."}\hthm{set} @{text "[simp, code]"}\rm:] ~ \\ |
53694 | 805 |
@{thm list.set(1)[no_vars]} \\ |
806 |
@{thm list.set(2)[no_vars]} |
|
53552 | 807 |
|
53798 | 808 |
\item[@{text "t."}\hthm{map} @{text "[simp, code]"}\rm:] ~ \\ |
53552 | 809 |
@{thm list.map(1)[no_vars]} \\ |
810 |
@{thm list.map(2)[no_vars]} |
|
811 |
||
53798 | 812 |
\item[@{text "t."}\hthm{rel\_inject} @{text "[simp, code]"}\rm:] ~ \\ |
53552 | 813 |
@{thm list.rel_inject(1)[no_vars]} \\ |
814 |
@{thm list.rel_inject(2)[no_vars]} |
|
815 |
||
53798 | 816 |
\item[@{text "t."}\hthm{rel\_distinct} @{text "[simp, code]"}\rm:] ~ \\ |
53552 | 817 |
@{thm list.rel_distinct(1)[no_vars]} \\ |
818 |
@{thm list.rel_distinct(2)[no_vars]} |
|
819 |
||
820 |
\end{description} |
|
821 |
\end{indentblock} |
|
53535 | 822 |
*} |
823 |
||
824 |
||
53621 | 825 |
subsubsection {* Inductive Theorems |
826 |
\label{sssec:inductive-theorems} *} |
|
53535 | 827 |
|
828 |
text {* |
|
53623 | 829 |
The inductive theorems are as follows: |
53544 | 830 |
|
53552 | 831 |
\begin{indentblock} |
53544 | 832 |
\begin{description} |
833 |
||
53642 | 834 |
\item[@{text "t."}\hthm{induct} @{text "[induct t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53544 | 835 |
@{thm list.induct[no_vars]} |
836 |
||
53642 | 837 |
\item[@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53544 | 838 |
Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
839 |
prove $m$ properties simultaneously. |
|
52828 | 840 |
|
53798 | 841 |
\item[@{text "t."}\hthm{fold} @{text "[simp, code]"}\rm:] ~ \\ |
53544 | 842 |
@{thm list.fold(1)[no_vars]} \\ |
843 |
@{thm list.fold(2)[no_vars]} |
|
844 |
||
53798 | 845 |
\item[@{text "t."}\hthm{rec} @{text "[simp, code]"}\rm:] ~ \\ |
53544 | 846 |
@{thm list.rec(1)[no_vars]} \\ |
847 |
@{thm list.rec(2)[no_vars]} |
|
848 |
||
849 |
\end{description} |
|
53552 | 850 |
\end{indentblock} |
53544 | 851 |
|
852 |
\noindent |
|
853 |
For convenience, @{command datatype_new} also provides the following collection: |
|
854 |
||
53552 | 855 |
\begin{indentblock} |
53544 | 856 |
\begin{description} |
857 |
||
858 |
\item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.rec} @{text t.fold} @{text t.map} @{text t.rel_inject}] ~ \\ |
|
53694 | 859 |
@{text t.rel_distinct} @{text t.set} |
53544 | 860 |
|
861 |
\end{description} |
|
53552 | 862 |
\end{indentblock} |
52828 | 863 |
*} |
864 |
||
52794 | 865 |
|
52827 | 866 |
subsection {* Compatibility Issues |
52824 | 867 |
\label{ssec:datatype-compatibility-issues} *} |
52794 | 868 |
|
52828 | 869 |
text {* |
53647 | 870 |
The command @{command datatype_new} was designed to be highly compatible with |
53752 | 871 |
\keyw{datatype}, to ease migration. There are nonetheless a number of |
53647 | 872 |
incompatibilities that may arise when porting to the new package: |
873 |
||
874 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
875 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
876 |
|
53647 | 877 |
\item \emph{The Standard ML interfaces are different.} Tools and extensions |
878 |
written to call the old ML interfaces will need to be adapted to the new |
|
879 |
interfaces. Little has been done so far in this direction. Whenever possible, it |
|
880 |
is recommended to use @{command datatype_new_compat} or \keyw{rep\_datatype} |
|
881 |
to register new-style datatypes as old-style datatypes. |
|
882 |
||
883 |
\item \emph{The recursor @{text "t_rec"} has a different signature for nested |
|
884 |
recursive datatypes.} In the old package, nested recursion was internally |
|
885 |
reduced to mutual recursion. This reduction was visible in the type of the |
|
886 |
recursor, used by \keyw{primrec}. In the new package, nested recursion is |
|
887 |
handled in a more modular fashion. The old-style recursor can be generated on |
|
888 |
demand using @{command primrec_new}, as explained in |
|
889 |
Section~\ref{sssec:primrec-nested-as-mutual-recursion}, if the recursion is via |
|
890 |
new-style datatypes. |
|
891 |
||
892 |
\item \emph{Accordingly, the induction principle is different for nested |
|
893 |
recursive datatypes.} Again, the old-style induction principle can be generated |
|
894 |
on demand using @{command primrec_new}, as explained in |
|
895 |
Section~\ref{sssec:primrec-nested-as-mutual-recursion}, if the recursion is via |
|
896 |
new-style datatypes. |
|
52828 | 897 |
|
53647 | 898 |
\item \emph{The internal constructions are completely different.} Proofs texts |
899 |
that unfold the definition of constants introduced by \keyw{datatype} will be |
|
900 |
difficult to port. |
|
901 |
||
902 |
\item \emph{A few theorems have different names.} |
|
903 |
The properties @{text t.cases} and @{text t.recs} have been renamed to |
|
904 |
@{text t.case} and @{text t.rec}. For non-mutually recursive datatypes, |
|
905 |
@{text t.inducts} is available as @{text t.induct}. |
|
906 |
For $m > 1$ mutually recursive datatypes, |
|
907 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m.inducts(i)"} has been renamed to |
|
908 |
@{text "t\<^sub>i.induct"}. |
|
909 |
||
910 |
\item \emph{The @{text t.simps} collection has been extended.} |
|
911 |
Previously available theorems are available at the same index. |
|
912 |
||
913 |
\item \emph{Variables in generated properties have different names.} This is |
|
914 |
rarely an issue, except in proof texts that refer to variable names in the |
|
915 |
@{text "[where \<dots>]"} attribute. The solution is to use the more robust |
|
916 |
@{text "[of \<dots>]"} syntax. |
|
917 |
\end{itemize} |
|
918 |
||
919 |
In the other direction, there is currently no way to register old-style |
|
920 |
datatypes as new-style datatypes. If the goal is to define new-style datatypes |
|
921 |
with nested recursion through old-style datatypes, the old-style |
|
922 |
datatypes can be registered as a BNF |
|
923 |
(Section~\ref{sec:registering-bounded-natural-functors}). If the goal is |
|
924 |
to derive discriminators and selectors, this can be achieved using @{command |
|
925 |
wrap_free_constructors} |
|
926 |
(Section~\ref{sec:deriving-destructors-and-theorems-for-free-constructors}). |
|
52828 | 927 |
*} |
928 |
||
52792 | 929 |
|
52827 | 930 |
section {* Defining Recursive Functions |
52805 | 931 |
\label{sec:defining-recursive-functions} *} |
932 |
||
933 |
text {* |
|
53644 | 934 |
Recursive functions over datatypes can be specified using @{command |
935 |
primrec_new}, which supports primitive recursion, or using the more general |
|
936 |
\keyw{fun} and \keyw{function} commands. Here, the focus is on @{command |
|
937 |
primrec_new}; the other two commands are described in a separate tutorial |
|
53646 | 938 |
\cite{isabelle-function}. |
52828 | 939 |
|
53621 | 940 |
%%% TODO: partial_function |
52805 | 941 |
*} |
52792 | 942 |
|
52805 | 943 |
|
53617 | 944 |
subsection {* Introductory Examples |
945 |
\label{ssec:primrec-introductory-examples} *} |
|
52828 | 946 |
|
53646 | 947 |
text {* |
948 |
Primitive recursion is illustrated through concrete examples based on the |
|
949 |
datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More |
|
950 |
examples can be found in the directory \verb|~~/src/HOL/BNF/Examples|. |
|
951 |
*} |
|
952 |
||
53621 | 953 |
|
954 |
subsubsection {* Nonrecursive Types |
|
955 |
\label{sssec:primrec-nonrecursive-types} *} |
|
52828 | 956 |
|
52841 | 957 |
text {* |
53621 | 958 |
Primitive recursion removes one layer of constructors on the left-hand side in |
959 |
each equation. For example: |
|
52841 | 960 |
*} |
961 |
||
962 |
primrec_new bool_of_trool :: "trool \<Rightarrow> bool" where |
|
53621 | 963 |
"bool_of_trool Faalse \<longleftrightarrow> False" | |
964 |
"bool_of_trool Truue \<longleftrightarrow> True" |
|
52841 | 965 |
|
53621 | 966 |
text {* \blankline *} |
52841 | 967 |
|
53025 | 968 |
primrec_new the_list :: "'a option \<Rightarrow> 'a list" where |
969 |
"the_list None = []" | |
|
970 |
"the_list (Some a) = [a]" |
|
52841 | 971 |
|
53621 | 972 |
text {* \blankline *} |
973 |
||
53025 | 974 |
primrec_new the_default :: "'a \<Rightarrow> 'a option \<Rightarrow> 'a" where |
975 |
"the_default d None = d" | |
|
976 |
"the_default _ (Some a) = a" |
|
52843 | 977 |
|
53621 | 978 |
text {* \blankline *} |
979 |
||
52841 | 980 |
primrec_new mirrror :: "('a, 'b, 'c) triple \<Rightarrow> ('c, 'b, 'a) triple" where |
981 |
"mirrror (Triple a b c) = Triple c b a" |
|
982 |
||
53621 | 983 |
text {* |
984 |
\noindent |
|
985 |
The equations can be specified in any order, and it is acceptable to leave out |
|
986 |
some cases, which are then unspecified. Pattern matching on the left-hand side |
|
987 |
is restricted to a single datatype, which must correspond to the same argument |
|
988 |
in all equations. |
|
989 |
*} |
|
52828 | 990 |
|
53621 | 991 |
|
992 |
subsubsection {* Simple Recursion |
|
993 |
\label{sssec:primrec-simple-recursion} *} |
|
52828 | 994 |
|
52841 | 995 |
text {* |
53621 | 996 |
For simple recursive types, recursive calls on a constructor argument are |
997 |
allowed on the right-hand side: |
|
52841 | 998 |
*} |
999 |
||
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1000 |
primrec_new replicate :: "nat \<Rightarrow> 'a \<Rightarrow> 'a list" where |
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1001 |
"replicate Zero _ = []" | |
53644 | 1002 |
"replicate (Suc n) x = x # replicate n x" |
52841 | 1003 |
|
53621 | 1004 |
text {* \blankline *} |
52843 | 1005 |
|
53332 | 1006 |
primrec_new at :: "'a list \<Rightarrow> nat \<Rightarrow> 'a" where |
53644 | 1007 |
"at (x # xs) j = |
52843 | 1008 |
(case j of |
53644 | 1009 |
Zero \<Rightarrow> x |
1010 |
| Suc j' \<Rightarrow> at xs j')" |
|
52843 | 1011 |
|
53621 | 1012 |
text {* \blankline *} |
1013 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1014 |
primrec_new (*<*)(in early) (*>*)tfold :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> ('a, 'b) tlist \<Rightarrow> 'b" where |
53644 | 1015 |
"tfold _ (TNil y) = y" | |
1016 |
"tfold f (TCons x xs) = f x (tfold f xs)" |
|
52841 | 1017 |
|
53025 | 1018 |
text {* |
53621 | 1019 |
\noindent |
1020 |
The next example is not primitive recursive, but it can be defined easily using |
|
53644 | 1021 |
\keyw{fun}. The @{command datatype_new_compat} command is needed to register |
1022 |
new-style datatypes for use with \keyw{fun} and \keyw{function} |
|
53621 | 1023 |
(Section~\ref{sssec:datatype-new-compat}): |
53025 | 1024 |
*} |
52828 | 1025 |
|
53621 | 1026 |
datatype_new_compat nat |
1027 |
||
1028 |
text {* \blankline *} |
|
1029 |
||
1030 |
fun at_least_two :: "nat \<Rightarrow> bool" where |
|
1031 |
"at_least_two (Suc (Suc _)) \<longleftrightarrow> True" | |
|
1032 |
"at_least_two _ \<longleftrightarrow> False" |
|
1033 |
||
1034 |
||
1035 |
subsubsection {* Mutual Recursion |
|
1036 |
\label{sssec:primrec-mutual-recursion} *} |
|
52828 | 1037 |
|
52841 | 1038 |
text {* |
53621 | 1039 |
The syntax for mutually recursive functions over mutually recursive datatypes |
1040 |
is straightforward: |
|
52841 | 1041 |
*} |
1042 |
||
1043 |
primrec_new |
|
53623 | 1044 |
nat_of_even_nat :: "even_nat \<Rightarrow> nat" and |
1045 |
nat_of_odd_nat :: "odd_nat \<Rightarrow> nat" |
|
52841 | 1046 |
where |
53623 | 1047 |
"nat_of_even_nat Even_Zero = Zero" | |
1048 |
"nat_of_even_nat (Even_Suc n) = Suc (nat_of_odd_nat n)" | |
|
1049 |
"nat_of_odd_nat (Odd_Suc n) = Suc (nat_of_even_nat n)" |
|
52841 | 1050 |
|
53752 | 1051 |
text {* \blankline *} |
1052 |
||
52841 | 1053 |
primrec_new |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1054 |
eval\<^sub>e :: "('a \<Rightarrow> int) \<Rightarrow> ('b \<Rightarrow> int) \<Rightarrow> ('a, 'b) exp \<Rightarrow> int" and |
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1055 |
eval\<^sub>t :: "('a \<Rightarrow> int) \<Rightarrow> ('b \<Rightarrow> int) \<Rightarrow> ('a, 'b) trm \<Rightarrow> int" and |
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1056 |
eval\<^sub>f :: "('a \<Rightarrow> int) \<Rightarrow> ('b \<Rightarrow> int) \<Rightarrow> ('a, 'b) fct \<Rightarrow> int" |
52841 | 1057 |
where |
1058 |
"eval\<^sub>e \<gamma> \<xi> (Term t) = eval\<^sub>t \<gamma> \<xi> t" | |
|
1059 |
"eval\<^sub>e \<gamma> \<xi> (Sum t e) = eval\<^sub>t \<gamma> \<xi> t + eval\<^sub>e \<gamma> \<xi> e" | |
|
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1060 |
"eval\<^sub>t \<gamma> \<xi> (Factor f) = eval\<^sub>f \<gamma> \<xi> f" | |
52841 | 1061 |
"eval\<^sub>t \<gamma> \<xi> (Prod f t) = eval\<^sub>f \<gamma> \<xi> f + eval\<^sub>t \<gamma> \<xi> t" | |
1062 |
"eval\<^sub>f \<gamma> _ (Const a) = \<gamma> a" | |
|
1063 |
"eval\<^sub>f _ \<xi> (Var b) = \<xi> b" | |
|
1064 |
"eval\<^sub>f \<gamma> \<xi> (Expr e) = eval\<^sub>e \<gamma> \<xi> e" |
|
1065 |
||
53621 | 1066 |
text {* |
1067 |
\noindent |
|
53647 | 1068 |
Mutual recursion is possible within a single type, using \keyw{fun}: |
53621 | 1069 |
*} |
52828 | 1070 |
|
53621 | 1071 |
fun |
1072 |
even :: "nat \<Rightarrow> bool" and |
|
1073 |
odd :: "nat \<Rightarrow> bool" |
|
1074 |
where |
|
1075 |
"even Zero = True" | |
|
1076 |
"even (Suc n) = odd n" | |
|
1077 |
"odd Zero = False" | |
|
1078 |
"odd (Suc n) = even n" |
|
1079 |
||
1080 |
||
1081 |
subsubsection {* Nested Recursion |
|
1082 |
\label{sssec:primrec-nested-recursion} *} |
|
1083 |
||
1084 |
text {* |
|
1085 |
In a departure from the old datatype package, nested recursion is normally |
|
1086 |
handled via the map functions of the nesting type constructors. For example, |
|
1087 |
recursive calls are lifted to lists using @{const map}: |
|
1088 |
*} |
|
52828 | 1089 |
|
52843 | 1090 |
(*<*) |
53644 | 1091 |
datatype_new 'a tree\<^sub>f\<^sub>f = Node\<^sub>f\<^sub>f (lbl\<^sub>f\<^sub>f: 'a) (sub\<^sub>f\<^sub>f: "'a tree\<^sub>f\<^sub>f list") |
52843 | 1092 |
(*>*) |
53028 | 1093 |
primrec_new at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" where |
1094 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
|
52843 | 1095 |
(case js of |
1096 |
[] \<Rightarrow> a |
|
53028 | 1097 |
| j # js' \<Rightarrow> at (map (\<lambda>t. at\<^sub>f\<^sub>f t js') ts) j)" |
52843 | 1098 |
|
53025 | 1099 |
text {* |
53647 | 1100 |
\noindent |
53621 | 1101 |
The next example features recursion through the @{text option} type. Although |
53623 | 1102 |
@{text option} is not a new-style datatype, it is registered as a BNF with the |
53621 | 1103 |
map function @{const option_map}: |
53025 | 1104 |
*} |
52843 | 1105 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1106 |
primrec_new (*<*)(in early) (*>*)sum_btree :: "('a\<Colon>{zero,plus}) btree \<Rightarrow> 'a" where |
52843 | 1107 |
"sum_btree (BNode a lt rt) = |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1108 |
a + the_default 0 (option_map sum_btree lt) + |
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1109 |
the_default 0 (option_map sum_btree rt)" |
52843 | 1110 |
|
53136 | 1111 |
text {* |
53621 | 1112 |
\noindent |
1113 |
The same principle applies for arbitrary type constructors through which |
|
1114 |
recursion is possible. Notably, the map function for the function type |
|
1115 |
(@{text \<Rightarrow>}) is simply composition (@{text "op \<circ>"}): |
|
53136 | 1116 |
*} |
52828 | 1117 |
|
53621 | 1118 |
primrec_new ftree_map :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
1119 |
"ftree_map f (FTLeaf x) = FTLeaf (f x)" | |
|
1120 |
"ftree_map f (FTNode g) = FTNode (ftree_map f \<circ> g)" |
|
52828 | 1121 |
|
52843 | 1122 |
text {* |
53621 | 1123 |
\noindent |
1124 |
(No such function is defined by the package because @{typ 'a} is dead in |
|
1125 |
@{typ "'a ftree"}, but we can easily do it ourselves.) |
|
1126 |
*} |
|
1127 |
||
1128 |
||
1129 |
subsubsection {* Nested-as-Mutual Recursion |
|
53644 | 1130 |
\label{sssec:primrec-nested-as-mutual-recursion} *} |
53621 | 1131 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1132 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1133 |
locale n2m begin |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1134 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1135 |
|
53621 | 1136 |
text {* |
1137 |
For compatibility with the old package, but also because it is sometimes |
|
1138 |
convenient in its own right, it is possible to treat nested recursive datatypes |
|
1139 |
as mutually recursive ones if the recursion takes place though new-style |
|
1140 |
datatypes. For example: |
|
52843 | 1141 |
*} |
1142 |
||
53331
20440c789759
prove theorem in the right context (that knows about local variables)
traytel
parents:
53330
diff
changeset
|
1143 |
primrec_new |
53647 | 1144 |
at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" and |
1145 |
ats\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f list \<Rightarrow> nat \<Rightarrow> nat list \<Rightarrow> 'a" |
|
52843 | 1146 |
where |
53647 | 1147 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
52843 | 1148 |
(case js of |
1149 |
[] \<Rightarrow> a |
|
53647 | 1150 |
| j # js' \<Rightarrow> ats\<^sub>f\<^sub>f ts j js')" | |
1151 |
"ats\<^sub>f\<^sub>f (t # ts) j = |
|
52843 | 1152 |
(case j of |
53647 | 1153 |
Zero \<Rightarrow> at\<^sub>f\<^sub>f t |
1154 |
| Suc j' \<Rightarrow> ats\<^sub>f\<^sub>f ts j')" |
|
52843 | 1155 |
|
53647 | 1156 |
text {* |
1157 |
\noindent |
|
1158 |
Appropriate induction principles are generated under the names |
|
1159 |
@{thm [source] "at\<^sub>f\<^sub>f.induct"}, |
|
1160 |
@{thm [source] "ats\<^sub>f\<^sub>f.induct"}, and |
|
1161 |
@{thm [source] "at\<^sub>f\<^sub>f_ats\<^sub>f\<^sub>f.induct"}. |
|
1162 |
||
1163 |
%%% TODO: Add recursors. |
|
1164 |
||
1165 |
Here is a second example: |
|
1166 |
*} |
|
53621 | 1167 |
|
53331
20440c789759
prove theorem in the right context (that knows about local variables)
traytel
parents:
53330
diff
changeset
|
1168 |
primrec_new |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1169 |
sum_btree :: "('a\<Colon>{zero,plus}) btree \<Rightarrow> 'a" and |
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1170 |
sum_btree_option :: "'a btree option \<Rightarrow> 'a" |
52843 | 1171 |
where |
1172 |
"sum_btree (BNode a lt rt) = |
|
53025 | 1173 |
a + sum_btree_option lt + sum_btree_option rt" | |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1174 |
"sum_btree_option None = 0" | |
53025 | 1175 |
"sum_btree_option (Some t) = sum_btree t" |
52843 | 1176 |
|
1177 |
text {* |
|
53621 | 1178 |
% * can pretend a nested type is mutually recursive (if purely inductive) |
1179 |
% * avoids the higher-order map |
|
1180 |
% * e.g. |
|
1181 |
||
53617 | 1182 |
% * this can always be avoided; |
1183 |
% * e.g. in our previous example, we first mapped the recursive |
|
1184 |
% calls, then we used a generic at function to retrieve the result |
|
1185 |
% |
|
1186 |
% * there's no hard-and-fast rule of when to use one or the other, |
|
1187 |
% just like there's no rule when to use fold and when to use |
|
1188 |
% primrec_new |
|
1189 |
% |
|
1190 |
% * higher-order approach, considering nesting as nesting, is more |
|
1191 |
% compositional -- e.g. we saw how we could reuse an existing polymorphic |
|
53647 | 1192 |
% at or the_default, whereas @{const ats\<^sub>f\<^sub>f} is much more specific |
53617 | 1193 |
% |
1194 |
% * but: |
|
1195 |
% * is perhaps less intuitive, because it requires higher-order thinking |
|
1196 |
% * may seem inefficient, and indeed with the code generator the |
|
1197 |
% mutually recursive version might be nicer |
|
1198 |
% * is somewhat indirect -- must apply a map first, then compute a result |
|
1199 |
% (cannot mix) |
|
53647 | 1200 |
% * the auxiliary functions like @{const ats\<^sub>f\<^sub>f} are sometimes useful in own right |
53617 | 1201 |
% |
1202 |
% * impact on automation unclear |
|
1203 |
% |
|
52843 | 1204 |
*} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1205 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1206 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1207 |
(*>*) |
52843 | 1208 |
|
52824 | 1209 |
|
53617 | 1210 |
subsection {* Command Syntax |
1211 |
\label{ssec:primrec-command-syntax} *} |
|
1212 |
||
1213 |
||
53621 | 1214 |
subsubsection {* \keyw{primrec\_new} |
1215 |
\label{sssec:primrec-new} *} |
|
52828 | 1216 |
|
1217 |
text {* |
|
53829 | 1218 |
\begin{matharray}{rcl} |
1219 |
@{command_def "primrec_new"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
1220 |
\end{matharray} |
|
52794 | 1221 |
|
52840 | 1222 |
@{rail " |
53829 | 1223 |
@@{command primrec_new} target? fixes \\ @'where' (@{syntax pr_equation} + '|') |
52840 | 1224 |
; |
53829 | 1225 |
@{syntax_def pr_equation}: thmdecl? prop |
52840 | 1226 |
"} |
52828 | 1227 |
*} |
1228 |
||
52840 | 1229 |
|
53619 | 1230 |
(* |
52840 | 1231 |
subsection {* Generated Theorems |
1232 |
\label{ssec:primrec-generated-theorems} *} |
|
52824 | 1233 |
|
52828 | 1234 |
text {* |
53617 | 1235 |
% * synthesized nonrecursive definition |
1236 |
% * user specification is rederived from it, exactly as entered |
|
1237 |
% |
|
1238 |
% * induct |
|
1239 |
% * mutualized |
|
1240 |
% * without some needless induction hypotheses if not used |
|
1241 |
% * fold, rec |
|
1242 |
% * mutualized |
|
52828 | 1243 |
*} |
53619 | 1244 |
*) |
1245 |
||
52824 | 1246 |
|
52840 | 1247 |
subsection {* Recursive Default Values for Selectors |
53623 | 1248 |
\label{ssec:primrec-recursive-default-values-for-selectors} *} |
52827 | 1249 |
|
1250 |
text {* |
|
1251 |
A datatype selector @{text un_D} can have a default value for each constructor |
|
1252 |
on which it is not otherwise specified. Occasionally, it is useful to have the |
|
1253 |
default value be defined recursively. This produces a chicken-and-egg situation |
|
53621 | 1254 |
that may seem unsolvable, because the datatype is not introduced yet at the |
52827 | 1255 |
moment when the selectors are introduced. Of course, we can always define the |
1256 |
selectors manually afterward, but we then have to state and prove all the |
|
1257 |
characteristic theorems ourselves instead of letting the package do it. |
|
1258 |
||
1259 |
Fortunately, there is a fairly elegant workaround that relies on overloading and |
|
1260 |
that avoids the tedium of manual derivations: |
|
1261 |
||
1262 |
\begin{enumerate} |
|
1263 |
\setlength{\itemsep}{0pt} |
|
1264 |
||
1265 |
\item |
|
1266 |
Introduce a fully unspecified constant @{text "un_D\<^sub>0 \<Colon> 'a"} using |
|
1267 |
@{keyword consts}. |
|
1268 |
||
1269 |
\item |
|
53535 | 1270 |
Define the datatype, specifying @{text "un_D\<^sub>0"} as the selector's default |
1271 |
value. |
|
52827 | 1272 |
|
1273 |
\item |
|
53535 | 1274 |
Define the behavior of @{text "un_D\<^sub>0"} on values of the newly introduced |
1275 |
datatype using the \keyw{overloading} command. |
|
52827 | 1276 |
|
1277 |
\item |
|
1278 |
Derive the desired equation on @{text un_D} from the characteristic equations |
|
1279 |
for @{text "un_D\<^sub>0"}. |
|
1280 |
\end{enumerate} |
|
1281 |
||
53619 | 1282 |
\noindent |
52827 | 1283 |
The following example illustrates this procedure: |
1284 |
*} |
|
1285 |
||
1286 |
consts termi\<^sub>0 :: 'a |
|
1287 |
||
53619 | 1288 |
text {* \blankline *} |
1289 |
||
53491 | 1290 |
datatype_new ('a, 'b) tlist = |
52827 | 1291 |
TNil (termi: 'b) (defaults ttl: TNil) |
53491 | 1292 |
| TCons (thd: 'a) (ttl : "('a, 'b) tlist") (defaults termi: "\<lambda>_ xs. termi\<^sub>0 xs") |
52827 | 1293 |
|
53619 | 1294 |
text {* \blankline *} |
1295 |
||
52827 | 1296 |
overloading |
53491 | 1297 |
termi\<^sub>0 \<equiv> "termi\<^sub>0 \<Colon> ('a, 'b) tlist \<Rightarrow> 'b" |
52827 | 1298 |
begin |
53491 | 1299 |
primrec_new termi\<^sub>0 :: "('a, 'b) tlist \<Rightarrow> 'b" where |
53621 | 1300 |
"termi\<^sub>0 (TNil y) = y" | |
1301 |
"termi\<^sub>0 (TCons x xs) = termi\<^sub>0 xs" |
|
52827 | 1302 |
end |
1303 |
||
53619 | 1304 |
text {* \blankline *} |
1305 |
||
52827 | 1306 |
lemma terminal_TCons[simp]: "termi (TCons x xs) = termi xs" |
1307 |
by (cases xs) auto |
|
1308 |
||
1309 |
||
53617 | 1310 |
(* |
52828 | 1311 |
subsection {* Compatibility Issues |
53617 | 1312 |
\label{ssec:primrec-compatibility-issues} *} |
52828 | 1313 |
|
1314 |
text {* |
|
53617 | 1315 |
% * different induction in nested case |
1316 |
% * solution: define nested-as-mutual functions with primrec, |
|
1317 |
% and look at .induct |
|
1318 |
% |
|
1319 |
% * different induction and recursor in nested case |
|
1320 |
% * only matters to low-level users; they can define a dummy function to force |
|
1321 |
% generation of mutualized recursor |
|
52828 | 1322 |
*} |
53617 | 1323 |
*) |
52794 | 1324 |
|
1325 |
||
52827 | 1326 |
section {* Defining Codatatypes |
52805 | 1327 |
\label{sec:defining-codatatypes} *} |
1328 |
||
1329 |
text {* |
|
53829 | 1330 |
Codatatypes can be specified using the @{command codatatype} command. The |
53623 | 1331 |
command is first illustrated through concrete examples featuring different |
1332 |
flavors of corecursion. More examples can be found in the directory |
|
1333 |
\verb|~~/src/HOL/BNF/Examples|. The \emph{Archive of Formal Proofs} also |
|
1334 |
includes some useful codatatypes, notably for lazy lists \cite{lochbihler-2010}. |
|
52805 | 1335 |
*} |
52792 | 1336 |
|
52824 | 1337 |
|
53617 | 1338 |
subsection {* Introductory Examples |
1339 |
\label{ssec:codatatype-introductory-examples} *} |
|
52794 | 1340 |
|
53623 | 1341 |
|
1342 |
subsubsection {* Simple Corecursion |
|
1343 |
\label{sssec:codatatype-simple-corecursion} *} |
|
1344 |
||
52805 | 1345 |
text {* |
53623 | 1346 |
Noncorecursive codatatypes coincide with the corresponding datatypes, so |
1347 |
they have no practical uses. \emph{Corecursive codatatypes} have the same syntax |
|
1348 |
as recursive datatypes, except for the command name. For example, here is the |
|
1349 |
definition of lazy lists: |
|
1350 |
*} |
|
1351 |
||
1352 |
codatatype (lset: 'a) llist (map: lmap rel: llist_all2) = |
|
1353 |
lnull: LNil (defaults ltl: LNil) |
|
1354 |
| LCons (lhd: 'a) (ltl: "'a llist") |
|
1355 |
||
1356 |
text {* |
|
1357 |
\noindent |
|
1358 |
Lazy lists can be infinite, such as @{text "LCons 0 (LCons 0 (\<dots>))"} and |
|
53647 | 1359 |
@{text "LCons 0 (LCons 1 (LCons 2 (\<dots>)))"}. Here is a related type, that of |
1360 |
infinite streams: |
|
1361 |
*} |
|
1362 |
||
1363 |
codatatype (sset: 'a) stream (map: smap rel: stream_all2) = |
|
1364 |
SCons (shd: 'a) (stl: "'a stream") |
|
1365 |
||
1366 |
text {* |
|
1367 |
\noindent |
|
1368 |
Another interesting type that can |
|
53623 | 1369 |
be defined as a codatatype is that of the extended natural numbers: |
1370 |
*} |
|
1371 |
||
53644 | 1372 |
codatatype enat = EZero | ESuc enat |
53623 | 1373 |
|
1374 |
text {* |
|
1375 |
\noindent |
|
1376 |
This type has exactly one infinite element, @{text "ESuc (ESuc (ESuc (\<dots>)))"}, |
|
1377 |
that represents $\infty$. In addition, it has finite values of the form |
|
1378 |
@{text "ESuc (\<dots> (ESuc EZero)\<dots>)"}. |
|
53675 | 1379 |
|
1380 |
Here is an example with many constructors: |
|
52805 | 1381 |
*} |
53623 | 1382 |
|
53675 | 1383 |
codatatype 'a process = |
1384 |
Fail |
|
1385 |
| Skip (cont: "'a process") |
|
1386 |
| Action (prefix: 'a) (cont: "'a process") |
|
1387 |
| Choice (left: "'a process") (right: "'a process") |
|
1388 |
||
53750 | 1389 |
text {* |
53829 | 1390 |
\noindent |
53750 | 1391 |
Notice that the @{const cont} selector is associated with both @{const Skip} |
1392 |
and @{const Choice}. |
|
1393 |
*} |
|
1394 |
||
53623 | 1395 |
|
1396 |
subsubsection {* Mutual Corecursion |
|
1397 |
\label{sssec:codatatype-mutual-corecursion} *} |
|
1398 |
||
1399 |
text {* |
|
1400 |
\noindent |
|
1401 |
The example below introduces a pair of \emph{mutually corecursive} types: |
|
1402 |
*} |
|
1403 |
||
1404 |
codatatype even_enat = Even_EZero | Even_ESuc odd_enat |
|
1405 |
and odd_enat = Odd_ESuc even_enat |
|
1406 |
||
1407 |
||
1408 |
subsubsection {* Nested Corecursion |
|
1409 |
\label{sssec:codatatype-nested-corecursion} *} |
|
1410 |
||
1411 |
text {* |
|
1412 |
\noindent |
|
53675 | 1413 |
The next examples feature \emph{nested corecursion}: |
53623 | 1414 |
*} |
1415 |
||
53644 | 1416 |
codatatype 'a tree\<^sub>i\<^sub>i = Node\<^sub>i\<^sub>i (lbl\<^sub>i\<^sub>i: 'a) (sub\<^sub>i\<^sub>i: "'a tree\<^sub>i\<^sub>i llist") |
53675 | 1417 |
|
53752 | 1418 |
text {* \blankline *} |
1419 |
||
53644 | 1420 |
codatatype 'a tree\<^sub>i\<^sub>s = Node\<^sub>i\<^sub>s (lbl\<^sub>i\<^sub>s: 'a) (sub\<^sub>i\<^sub>s: "'a tree\<^sub>i\<^sub>s fset") |
52805 | 1421 |
|
53752 | 1422 |
text {* \blankline *} |
1423 |
||
53675 | 1424 |
codatatype 'a state_machine = |
53751 | 1425 |
State_Machine (accept: bool) (trans: "'a \<Rightarrow> 'a state_machine") |
53675 | 1426 |
|
52824 | 1427 |
|
53617 | 1428 |
subsection {* Command Syntax |
1429 |
\label{ssec:codatatype-command-syntax} *} |
|
52805 | 1430 |
|
53619 | 1431 |
|
53621 | 1432 |
subsubsection {* \keyw{codatatype} |
1433 |
\label{sssec:codatatype} *} |
|
53619 | 1434 |
|
52824 | 1435 |
text {* |
53829 | 1436 |
\begin{matharray}{rcl} |
1437 |
@{command_def "codatatype"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
1438 |
\end{matharray} |
|
1439 |
||
1440 |
@{rail " |
|
1441 |
@@{command codatatype} target? \\ |
|
1442 |
(@{syntax dt_name} '=' (@{syntax ctor} + '|') + @'and') |
|
1443 |
"} |
|
1444 |
||
1445 |
\noindent |
|
52827 | 1446 |
Definitions of codatatypes have almost exactly the same syntax as for datatypes |
53829 | 1447 |
(Section~\ref{ssec:datatype-command-syntax}). The @{text "no_discs_sels"} option |
1448 |
is not available, because destructors are a crucial notion for codatatypes. |
|
53623 | 1449 |
*} |
1450 |
||
1451 |
||
1452 |
subsection {* Generated Constants |
|
1453 |
\label{ssec:codatatype-generated-constants} *} |
|
1454 |
||
1455 |
text {* |
|
1456 |
Given a codatatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
|
1457 |
with $m > 0$ live type variables and $n$ constructors @{text "t.C\<^sub>1"}, |
|
1458 |
\ldots, @{text "t.C\<^sub>n"}, the same auxiliary constants are generated as for |
|
1459 |
datatypes (Section~\ref{ssec:datatype-generated-constants}), except that the |
|
1460 |
iterator and the recursor are replaced by dual concepts: |
|
1461 |
||
1462 |
\begin{itemize} |
|
1463 |
\setlength{\itemsep}{0pt} |
|
1464 |
||
1465 |
\item \relax{Coiterator}: @{text t_unfold} |
|
1466 |
||
1467 |
\item \relax{Corecursor}: @{text t_corec} |
|
1468 |
||
1469 |
\end{itemize} |
|
1470 |
*} |
|
1471 |
||
1472 |
||
1473 |
subsection {* Generated Theorems |
|
1474 |
\label{ssec:codatatype-generated-theorems} *} |
|
1475 |
||
1476 |
text {* |
|
53829 | 1477 |
The characteristic theorems generated by @{command codatatype} are grouped in |
53623 | 1478 |
three broad categories: |
1479 |
||
1480 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1481 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1482 |
|
53623 | 1483 |
\item The \emph{free constructor theorems} are properties about the constructors |
1484 |
and destructors that can be derived for any freely generated type. |
|
1485 |
||
1486 |
\item The \emph{functorial theorems} are properties of datatypes related to |
|
1487 |
their BNF nature. |
|
1488 |
||
1489 |
\item The \emph{coinductive theorems} are properties of datatypes related to |
|
1490 |
their coinductive nature. |
|
1491 |
\end{itemize} |
|
1492 |
||
1493 |
\noindent |
|
1494 |
The first two categories are exactly as for datatypes and are described in |
|
53642 | 1495 |
Sections |
1496 |
\ref{sssec:free-constructor-theorems}~and~\ref{sssec:functorial-theorems}. |
|
52824 | 1497 |
*} |
1498 |
||
53617 | 1499 |
|
53623 | 1500 |
subsubsection {* Coinductive Theorems |
1501 |
\label{sssec:coinductive-theorems} *} |
|
1502 |
||
1503 |
text {* |
|
1504 |
The coinductive theorems are as follows: |
|
1505 |
||
1506 |
\begin{indentblock} |
|
1507 |
\begin{description} |
|
1508 |
||
53643 | 1509 |
\item[\begin{tabular}{@ {}l@ {}} |
1510 |
@{text "t."}\hthm{coinduct} @{text "[coinduct t, consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1511 |
\phantom{@{text "t."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1512 |
\end{tabular}] ~ \\ |
|
53623 | 1513 |
@{thm llist.coinduct[no_vars]} |
53617 | 1514 |
|
53643 | 1515 |
\item[\begin{tabular}{@ {}l@ {}} |
1516 |
@{text "t."}\hthm{strong\_coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1517 |
\phantom{@{text "t."}\hthm{strong\_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1518 |
\end{tabular}] ~ \\ |
|
1519 |
@{thm llist.strong_coinduct[no_vars]} |
|
53617 | 1520 |
|
53643 | 1521 |
\item[\begin{tabular}{@ {}l@ {}} |
1522 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m, case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"} \\ |
|
1523 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{strong\_coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1524 |
\phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{strong\_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1525 |
\end{tabular}] ~ \\ |
|
1526 |
Given $m > 1$ mutually corecursive codatatypes, these coinduction rules can be |
|
1527 |
used to prove $m$ properties simultaneously. |
|
1528 |
||
1529 |
\item[@{text "t."}\hthm{unfold} \rm(@{text "[simp]"})\rm:] ~ \\ |
|
53623 | 1530 |
@{thm llist.unfold(1)[no_vars]} \\ |
1531 |
@{thm llist.unfold(2)[no_vars]} |
|
1532 |
||
53643 | 1533 |
\item[@{text "t."}\hthm{corec} (@{text "[simp]"})\rm:] ~ \\ |
53623 | 1534 |
@{thm llist.corec(1)[no_vars]} \\ |
1535 |
@{thm llist.corec(2)[no_vars]} |
|
1536 |
||
53703 | 1537 |
\item[@{text "t."}\hthm{disc\_unfold}\rm:] ~ \\ |
53643 | 1538 |
@{thm llist.disc_unfold(1)[no_vars]} \\ |
1539 |
@{thm llist.disc_unfold(2)[no_vars]} |
|
1540 |
||
53703 | 1541 |
\item[@{text "t."}\hthm{disc\_corec}\rm:] ~ \\ |
53643 | 1542 |
@{thm llist.disc_corec(1)[no_vars]} \\ |
1543 |
@{thm llist.disc_corec(2)[no_vars]} |
|
1544 |
||
1545 |
\item[@{text "t."}\hthm{disc\_unfold\_iff} @{text "[simp]"}\rm:] ~ \\ |
|
1546 |
@{thm llist.disc_unfold_iff(1)[no_vars]} \\ |
|
1547 |
@{thm llist.disc_unfold_iff(2)[no_vars]} |
|
1548 |
||
1549 |
\item[@{text "t."}\hthm{disc\_corec\_iff} @{text "[simp]"}\rm:] ~ \\ |
|
1550 |
@{thm llist.disc_corec_iff(1)[no_vars]} \\ |
|
1551 |
@{thm llist.disc_corec_iff(2)[no_vars]} |
|
1552 |
||
1553 |
\item[@{text "t."}\hthm{sel\_unfold} @{text "[simp]"}\rm:] ~ \\ |
|
1554 |
@{thm llist.sel_unfold(1)[no_vars]} \\ |
|
1555 |
@{thm llist.sel_unfold(2)[no_vars]} |
|
1556 |
||
1557 |
\item[@{text "t."}\hthm{sel\_corec} @{text "[simp]"}\rm:] ~ \\ |
|
1558 |
@{thm llist.sel_corec(1)[no_vars]} \\ |
|
1559 |
@{thm llist.sel_corec(2)[no_vars]} |
|
1560 |
||
53623 | 1561 |
\end{description} |
1562 |
\end{indentblock} |
|
1563 |
||
1564 |
\noindent |
|
53829 | 1565 |
For convenience, @{command codatatype} also provides the following collection: |
53623 | 1566 |
|
1567 |
\begin{indentblock} |
|
1568 |
\begin{description} |
|
1569 |
||
53643 | 1570 |
\item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.corec}$^*$ @{text t.disc_corec}] ~ \\ |
1571 |
@{text t.disc_corec_iff} @{text t.sel_corec} @{text t.unfold}$^*$ @{text t.disc_unfold} @{text t.disc_unfold_iff} ~ \\ |
|
53694 | 1572 |
@{text t.sel_unfold} @{text t.map} @{text t.rel_inject} @{text t.rel_distinct} @{text t.set} |
53623 | 1573 |
|
1574 |
\end{description} |
|
1575 |
\end{indentblock} |
|
1576 |
*} |
|
52805 | 1577 |
|
1578 |
||
52827 | 1579 |
section {* Defining Corecursive Functions |
52805 | 1580 |
\label{sec:defining-corecursive-functions} *} |
1581 |
||
1582 |
text {* |
|
53753
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1583 |
Corecursive functions can be specified using @{command primcorec} and |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1584 |
@{command primcorecursive}, which support primitive corecursion, or using the |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1585 |
more general \keyw{partial\_function} command. Here, the focus is on |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1586 |
the former two. More examples can be found in the directory |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1587 |
\verb|~~/src/HOL/BNF/Examples|. |
53644 | 1588 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1589 |
Whereas recursive functions consume datatypes one constructor at a time, |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1590 |
corecursive functions construct codatatypes one constructor at a time. |
53752 | 1591 |
Partly reflecting a lack of agreement among proponents of coalgebraic methods, |
1592 |
Isabelle supports three competing syntaxes for specifying a function $f$: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1593 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1594 |
\begin{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1595 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1596 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1597 |
\abovedisplayskip=.5\abovedisplayskip |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1598 |
\belowdisplayskip=.5\belowdisplayskip |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1599 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1600 |
\item The \emph{destructor view} specifies $f$ by implications of the form |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1601 |
\[@{text "\<dots> \<Longrightarrow> is_C\<^sub>j (f x\<^sub>1 \<dots> x\<^sub>n)"}\] and |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1602 |
equations of the form |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1603 |
\[@{text "un_C\<^sub>ji (f x\<^sub>1 \<dots> x\<^sub>n) = \<dots>"}\] |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1604 |
This style is popular in the coalgebraic literature. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1605 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1606 |
\item The \emph{constructor view} specifies $f$ by equations of the form |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1607 |
\[@{text "\<dots> \<Longrightarrow> f x\<^sub>1 \<dots> x\<^sub>n = C \<dots>"}\] |
53752 | 1608 |
This style is often more concise than the previous one. |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1609 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1610 |
\item The \emph{code view} specifies $f$ by a single equation of the form |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1611 |
\[@{text "f x\<^sub>1 \<dots> x\<^sub>n = \<dots>"}\] |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1612 |
with restrictions on the format of the right-hand side. Lazy functional |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1613 |
programming languages such as Haskell support a generalized version of this |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1614 |
style. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1615 |
\end{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1616 |
|
53753
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1617 |
All three styles are available as input syntax. Whichever syntax is chosen, |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1618 |
characteristic theorems for all three styles are generated. |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1619 |
|
53644 | 1620 |
\begin{framed} |
1621 |
\noindent |
|
53753
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1622 |
\textbf{Warning:}\enskip The @{command primcorec} and @{command primcorecursive} |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1623 |
commands are under development. Some of the functionality described here is |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1624 |
vaporware. An alternative is to define corecursive functions directly using the |
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
1625 |
generated @{text t_unfold} or @{text t_corec} combinators. |
53644 | 1626 |
\end{framed} |
52828 | 1627 |
|
1628 |
%%% TODO: partial_function? E.g. for defining tail recursive function on lazy |
|
1629 |
%%% lists (cf. terminal0 in TLList.thy) |
|
52805 | 1630 |
*} |
1631 |
||
52824 | 1632 |
|
53617 | 1633 |
subsection {* Introductory Examples |
1634 |
\label{ssec:primcorec-introductory-examples} *} |
|
52805 | 1635 |
|
53646 | 1636 |
text {* |
1637 |
Primitive corecursion is illustrated through concrete examples based on the |
|
1638 |
codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1639 |
examples can be found in the directory \verb|~~/src/HOL/BNF/Examples|. The code |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1640 |
view is favored in the examples below. Sections |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1641 |
\ref{ssec:primrec-constructor-view} and \ref{ssec:primrec-destructor-view} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1642 |
present the same examples expressed using the constructor and destructor views. |
53646 | 1643 |
*} |
1644 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1645 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1646 |
locale code_view |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1647 |
begin |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1648 |
(*>*) |
53644 | 1649 |
|
1650 |
subsubsection {* Simple Corecursion |
|
1651 |
\label{sssec:primcorec-simple-corecursion} *} |
|
1652 |
||
53646 | 1653 |
text {* |
53752 | 1654 |
Following the code view, corecursive calls are allowed on the right-hand side as |
1655 |
long as they occur under a constructor, which itself appears either directly to |
|
1656 |
the right of the equal sign or in a conditional expression: |
|
53646 | 1657 |
*} |
1658 |
||
53826 | 1659 |
primcorec literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
53647 | 1660 |
"literate f x = LCons x (literate f (f x))" |
1661 |
||
53677 | 1662 |
text {* \blankline *} |
1663 |
||
53826 | 1664 |
primcorec siterate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a stream" where |
53647 | 1665 |
"siterate f x = SCons x (siterate f (f x))" |
53644 | 1666 |
|
53646 | 1667 |
text {* |
1668 |
\noindent |
|
1669 |
The constructor ensures that progress is made---i.e., the function is |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1670 |
\emph{productive}. The above functions compute the infinite lazy list or stream |
53646 | 1671 |
@{text "[x, f x, f (f x), \<dots>]"}. Productivity guarantees that prefixes |
1672 |
@{text "[x, f x, f (f x), \<dots>, (f ^^ k) x]"} of arbitrary finite length |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1673 |
@{text k} can be computed by unfolding the code equation a finite number of |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1674 |
times. The period (\keyw{.}) at the end of the commands discharge the zero proof |
53647 | 1675 |
obligations. |
53646 | 1676 |
|
53752 | 1677 |
Corecursive functions construct codatatype values, but nothing prevents them |
1678 |
from also consuming such values. The following function drops ever second |
|
53675 | 1679 |
element in a stream: |
1680 |
*} |
|
1681 |
||
53826 | 1682 |
primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
53675 | 1683 |
"every_snd s = SCons (shd s) (stl (stl s))" |
1684 |
||
1685 |
text {* |
|
53752 | 1686 |
\noindent |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1687 |
Constructs such as @{text "let"}---@{text "in"}, @{text |
53646 | 1688 |
"if"}---@{text "then"}---@{text "else"}, and @{text "case"}---@{text "of"} may |
1689 |
appear around constructors that guard corecursive calls: |
|
1690 |
*} |
|
1691 |
||
53826 | 1692 |
primcorec_notyet lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53644 | 1693 |
"lappend xs ys = |
1694 |
(case xs of |
|
1695 |
LNil \<Rightarrow> ys |
|
1696 |
| LCons x xs' \<Rightarrow> LCons x (lappend xs' ys))" |
|
1697 |
||
53646 | 1698 |
text {* |
53752 | 1699 |
\noindent |
53646 | 1700 |
Corecursion is useful to specify not only functions but also infinite objects: |
1701 |
*} |
|
1702 |
||
53826 | 1703 |
primcorec infty :: enat where |
53644 | 1704 |
"infty = ESuc infty" |
1705 |
||
53646 | 1706 |
text {* |
53752 | 1707 |
\noindent |
1708 |
The example below constructs a pseudorandom process value. It takes a stream of |
|
53675 | 1709 |
actions (@{text s}), a pseudorandom function generator (@{text f}), and a |
1710 |
pseudorandom seed (@{text n}): |
|
1711 |
*} |
|
1712 |
||
53826 | 1713 |
primcorec_notyet |
53752 | 1714 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
1715 |
where |
|
53675 | 1716 |
"random_process s f n = |
1717 |
(if n mod 4 = 0 then |
|
1718 |
Fail |
|
1719 |
else if n mod 4 = 1 then |
|
1720 |
Skip (random_process s f (f n)) |
|
1721 |
else if n mod 4 = 2 then |
|
1722 |
Action (shd s) (random_process (stl s) f (f n)) |
|
1723 |
else |
|
1724 |
Choice (random_process (every_snd s) (f \<circ> f) (f n)) |
|
1725 |
(random_process (every_snd (stl s)) (f \<circ> f) (f (f n))))" |
|
1726 |
||
1727 |
text {* |
|
1728 |
\noindent |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1729 |
The main disadvantage of the code view is that the conditions are tested |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1730 |
sequentially. This is visible in the generated theorems. The constructor and |
53752 | 1731 |
destructor views offer nonsequential alternatives. |
53675 | 1732 |
*} |
1733 |
||
53644 | 1734 |
|
1735 |
subsubsection {* Mutual Corecursion |
|
1736 |
\label{sssec:primcorec-mutual-corecursion} *} |
|
1737 |
||
53647 | 1738 |
text {* |
1739 |
The syntax for mutually corecursive functions over mutually corecursive |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1740 |
datatypes is unsurprising: |
53647 | 1741 |
*} |
1742 |
||
53826 | 1743 |
primcorec |
53644 | 1744 |
even_infty :: even_enat and |
1745 |
odd_infty :: odd_enat |
|
1746 |
where |
|
1747 |
"even_infty = Even_ESuc odd_infty" | |
|
1748 |
"odd_infty = Odd_ESuc even_infty" |
|
1749 |
||
1750 |
||
1751 |
subsubsection {* Nested Corecursion |
|
1752 |
\label{sssec:primcorec-nested-corecursion} *} |
|
1753 |
||
53647 | 1754 |
text {* |
1755 |
The next pair of examples generalize the @{const literate} and @{const siterate} |
|
1756 |
functions (Section~\ref{sssec:primcorec-nested-corecursion}) to possibly |
|
1757 |
infinite trees in which subnodes are organized either as a lazy list (@{text |
|
1758 |
tree\<^sub>i\<^sub>i}) or as a finite set (@{text tree\<^sub>i\<^sub>s}): |
|
1759 |
*} |
|
1760 |
||
53826 | 1761 |
primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
53644 | 1762 |
"iterate\<^sub>i\<^sub>i f x = Node\<^sub>i\<^sub>i x (lmap (iterate\<^sub>i\<^sub>i f) (f x))" |
1763 |
||
53677 | 1764 |
text {* \blankline *} |
1765 |
||
53826 | 1766 |
primcorec iterate\<^sub>i\<^sub>s :: "('a \<Rightarrow> 'a fset) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>s" where |
53644 | 1767 |
"iterate\<^sub>i\<^sub>s f x = Node\<^sub>i\<^sub>s x (fmap (iterate\<^sub>i\<^sub>s f) (f x))" |
1768 |
||
52805 | 1769 |
text {* |
53752 | 1770 |
\noindent |
53675 | 1771 |
Deterministic finite automata (DFAs) are usually defined as 5-tuples |
1772 |
@{text "(Q, \<Sigma>, \<delta>, q\<^sub>0, F)"}, where @{text Q} is a finite set of states, |
|
1773 |
@{text \<Sigma>} is a finite alphabet, @{text \<delta>} is a transition function, @{text q\<^sub>0} |
|
1774 |
is an initial state, and @{text F} is a set of final states. The following |
|
1775 |
function translates a DFA into a @{type state_machine}: |
|
1776 |
*} |
|
1777 |
||
53826 | 1778 |
primcorec (*<*)(in early) (*>*) |
53752 | 1779 |
sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a state_machine" |
1780 |
where |
|
1781 |
"sm_of_dfa \<delta> F q = State_Machine (q \<in> F) (sm_of_dfa \<delta> F o \<delta> q)" |
|
53675 | 1782 |
|
53751 | 1783 |
text {* |
1784 |
\noindent |
|
1785 |
The map function for the function type (@{text \<Rightarrow>}) is composition |
|
53752 | 1786 |
(@{text "op \<circ>"}). For convenience, corecursion through functions can be |
1787 |
expressed using @{text \<lambda>}-expressions and function application rather |
|
1788 |
than composition. For example: |
|
53751 | 1789 |
*} |
1790 |
||
53826 | 1791 |
primcorec |
53752 | 1792 |
sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a state_machine" |
1793 |
where |
|
1794 |
"sm_of_dfa \<delta> F q = State_Machine (q \<in> F) (sm_of_dfa \<delta> F o \<delta> q)" |
|
1795 |
||
1796 |
text {* \blankline *} |
|
1797 |
||
53826 | 1798 |
primcorec empty_sm :: "'a state_machine" where |
53752 | 1799 |
"empty_sm = State_Machine False (\<lambda>_. empty_sm)" |
53751 | 1800 |
|
53752 | 1801 |
text {* \blankline *} |
1802 |
||
53826 | 1803 |
primcorec not_sm :: "'a state_machine \<Rightarrow> 'a state_machine" where |
53752 | 1804 |
"not_sm M = State_Machine (\<not> accept M) (\<lambda>a. not_sm (trans M a))" |
53751 | 1805 |
|
53752 | 1806 |
text {* \blankline *} |
1807 |
||
53826 | 1808 |
primcorec |
53752 | 1809 |
or_sm :: "'a state_machine \<Rightarrow> 'a state_machine \<Rightarrow> 'a state_machine" |
1810 |
where |
|
1811 |
"or_sm M N = |
|
53751 | 1812 |
State_Machine (accept M \<or> accept N) |
53752 | 1813 |
(\<lambda>a. or_sm (trans M a) (trans N a))" |
53751 | 1814 |
|
53644 | 1815 |
|
1816 |
subsubsection {* Nested-as-Mutual Corecursion |
|
1817 |
\label{sssec:primcorec-nested-as-mutual-corecursion} *} |
|
1818 |
||
53647 | 1819 |
text {* |
1820 |
Just as it is possible to recurse over nested recursive datatypes as if they |
|
1821 |
were mutually recursive |
|
1822 |
(Section~\ref{sssec:primrec-nested-as-mutual-recursion}), it is possible to |
|
53752 | 1823 |
pretend that nested codatatypes are mutually corecursive. For example: |
53647 | 1824 |
*} |
1825 |
||
53826 | 1826 |
primcorec_notyet |
53644 | 1827 |
iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" and |
1828 |
iterates\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a llist \<Rightarrow> 'a tree\<^sub>i\<^sub>i llist" |
|
1829 |
where |
|
1830 |
"iterate\<^sub>i\<^sub>i f x = Node\<^sub>i\<^sub>i x (iterates\<^sub>i\<^sub>i f (f x))" | |
|
1831 |
"iterates\<^sub>i\<^sub>i f xs = |
|
1832 |
(case xs of |
|
1833 |
LNil \<Rightarrow> LNil |
|
1834 |
| LCons x xs' \<Rightarrow> LCons (iterate\<^sub>i\<^sub>i f x) (iterates\<^sub>i\<^sub>i f xs'))" |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1835 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1836 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1837 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1838 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1839 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1840 |
subsubsection {* Constructor View |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1841 |
\label{ssec:primrec-constructor-view} *} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1842 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1843 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1844 |
locale ctr_view = code_view |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1845 |
begin |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1846 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1847 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1848 |
text {* |
53750 | 1849 |
The constructor view is similar to the code view, but there is one separate |
1850 |
conditional equation per constructor rather than a single unconditional |
|
1851 |
equation. Examples that rely on a single constructor, such as @{const literate} |
|
1852 |
and @{const siterate}, are identical in both styles. |
|
1853 |
||
1854 |
Here is an example where there is a difference: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1855 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1856 |
|
53826 | 1857 |
primcorec lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1858 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lappend xs ys = LNil" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1859 |
"_ \<Longrightarrow> lappend xs ys = LCons (lhd (if lnull xs then ys else xs)) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1860 |
(if xs = LNil then ltl ys else lappend (ltl xs) ys)" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1861 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1862 |
text {* |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1863 |
\noindent |
53752 | 1864 |
With the constructor view, we must distinguish between the @{const LNil} and |
1865 |
the @{const LCons} case. The condition for @{const LCons} is |
|
1866 |
left implicit, as the negation of that for @{const LNil}. |
|
53750 | 1867 |
|
1868 |
For this example, the constructor view is slighlty more involved than the |
|
1869 |
code equation. Recall the code view version presented in |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1870 |
Section~\ref{sssec:primcorec-simple-corecursion}. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1871 |
% TODO: \[{thm code_view.lappend.code}\] |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1872 |
The constructor view requires us to analyze the second argument (@{term ys}). |
53752 | 1873 |
The code equation generated from the constructor view also suffers from this. |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1874 |
% TODO: \[{thm lappend.code}\] |
53750 | 1875 |
|
53752 | 1876 |
In contrast, the next example is arguably more naturally expressed in the |
1877 |
constructor view: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1878 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1879 |
|
53826 | 1880 |
primcorec_notyet |
53752 | 1881 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
1882 |
where |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1883 |
"n mod 4 = 0 \<Longrightarrow> random_process s f n = Fail" | |
53752 | 1884 |
"n mod 4 = 1 \<Longrightarrow> |
1885 |
random_process s f n = Skip (random_process s f (f n))" | |
|
1886 |
"n mod 4 = 2 \<Longrightarrow> |
|
1887 |
random_process s f n = Action (shd s) (random_process (stl s) f (f n))" | |
|
1888 |
"n mod 4 = 3 \<Longrightarrow> |
|
1889 |
random_process s f n = Choice (random_process (every_snd s) f (f n)) |
|
53826 | 1890 |
(random_process (every_snd (stl s)) f (f n))" |
1891 |
(*<*) |
|
53644 | 1892 |
end |
1893 |
(*>*) |
|
52805 | 1894 |
|
53750 | 1895 |
text {* |
53752 | 1896 |
\noindent |
53750 | 1897 |
Since there is no sequentiality, we can apply the equation for @{const Choice} |
53752 | 1898 |
without having first to discharge @{term "n mod (4\<Colon>int) \<noteq> 0"}, |
1899 |
@{term "n mod (4\<Colon>int) \<noteq> 1"}, and |
|
1900 |
@{term "n mod (4\<Colon>int) \<noteq> 2"}. |
|
53750 | 1901 |
The price to pay for this elegance is that we must discharge exclusivity proof |
1902 |
obligations, one for each pair of conditions |
|
53752 | 1903 |
@{term "(n mod (4\<Colon>int) = i, n mod (4\<Colon>int) = j)"} |
1904 |
with @{term "i < j"}. If we prefer not to discharge any obligations, we can |
|
1905 |
enable the @{text "sequential"} option. This pushes the problem to the users of |
|
1906 |
the generated properties. |
|
53750 | 1907 |
%Here are more examples to conclude: |
1908 |
*} |
|
1909 |
||
52824 | 1910 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1911 |
subsubsection {* Destructor View |
53752 | 1912 |
\label{ssec:primrec-destructor-view} *} |
1913 |
||
1914 |
(*<*) |
|
1915 |
locale dest_view |
|
1916 |
begin |
|
1917 |
(*>*) |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1918 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1919 |
text {* |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1920 |
The destructor view is in many respects dual to the constructor view. Conditions |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1921 |
determine which constructor to choose, and these conditions are interpreted |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1922 |
sequentially or not depending on the @{text "sequential"} option. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1923 |
Consider the following examples: |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1924 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1925 |
|
53826 | 1926 |
primcorec literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1927 |
"\<not> lnull (literate _ x)" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1928 |
"lhd (literate _ x) = x" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1929 |
"ltl (literate f x) = literate f (f x)" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1930 |
|
53752 | 1931 |
text {* \blankline *} |
1932 |
||
53826 | 1933 |
primcorec siterate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a stream" where |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1934 |
"shd (siterate _ x) = x" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1935 |
"stl (siterate f x) = siterate f (f x)" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1936 |
|
53752 | 1937 |
text {* \blankline *} |
1938 |
||
53826 | 1939 |
primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1940 |
"shd (every_snd s) = shd s" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1941 |
"stl (every_snd s) = stl (stl s)" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1942 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1943 |
text {* |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1944 |
\noindent |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1945 |
The first formula in the @{const literate} specification indicates which |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1946 |
constructor to choose. For @{const siterate} and @{const every_snd}, no such |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1947 |
formula is necessary, since the type has only one constructor. The last two |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1948 |
formulas are equations specifying the value of the result for the relevant |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1949 |
selectors. Corecursive calls appear directly to the right of the equal sign. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1950 |
Their arguments are unrestricted. |
53750 | 1951 |
|
1952 |
The next example shows how to specify functions that rely on more than one |
|
1953 |
constructor: |
|
1954 |
*} |
|
1955 |
||
53826 | 1956 |
primcorec lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53750 | 1957 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lnull (lappend xs ys)" | |
1958 |
"lhd (lappend xs ys) = lhd (if lnull xs then ys else xs)" | |
|
1959 |
"ltl (lappend xs ys) = (if xs = LNil then ltl ys else lappend (ltl xs) ys)" |
|
1960 |
||
1961 |
text {* |
|
1962 |
\noindent |
|
1963 |
For a codatatype with $n$ constructors, it is sufficient to specify $n - 1$ |
|
1964 |
discriminator formulas. The command will then assume that the remaining |
|
1965 |
constructor should be taken otherwise. This can be made explicit by adding |
|
1966 |
*} |
|
1967 |
||
1968 |
(*<*) |
|
1969 |
end |
|
1970 |
||
53826 | 1971 |
primcorec lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53750 | 1972 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lnull (lappend xs ys)" | |
1973 |
(*>*) |
|
53752 | 1974 |
"_ \<Longrightarrow> \<not> lnull (lappend xs ys)" |
1975 |
(*<*) | |
|
53750 | 1976 |
"lhd (lappend xs ys) = lhd (if lnull xs then ys else xs)" | |
1977 |
"ltl (lappend xs ys) = (if xs = LNil then ltl ys else lappend (ltl xs) ys)" |
|
1978 |
||
1979 |
context dest_view begin |
|
1980 |
(*>*) |
|
1981 |
||
1982 |
text {* |
|
1983 |
\noindent |
|
53752 | 1984 |
to the specification. The generated selector theorems are conditional. |
1985 |
||
1986 |
The next example illustrates how to cope with selectors defined for several |
|
53750 | 1987 |
constructors: |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1988 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1989 |
|
53826 | 1990 |
primcorec_notyet |
53752 | 1991 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
1992 |
where |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1993 |
"n mod 4 = 0 \<Longrightarrow> is_Fail (random_process s f n)" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1994 |
"n mod 4 = 1 \<Longrightarrow> is_Skip (random_process s f n)" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1995 |
"n mod 4 = 2 \<Longrightarrow> is_Action (random_process s f n)" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1996 |
"n mod 4 = 3 \<Longrightarrow> is_Choice (random_process s f n)" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1997 |
"cont (random_process s f n) = random_process s f (f n)" (* of Skip FIXME *) | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1998 |
"prefix (random_process s f n) = shd s" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1999 |
"cont (random_process s f n) = random_process (stl s) f (f n)" (* of Action FIXME *) | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2000 |
"left (random_process s f n) = random_process (every_snd s) f (f n)" | |
53752 | 2001 |
"right (random_process s f n) = random_process (every_snd (stl s)) f (f n)" (*<*) |
2002 |
(*>*) |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2003 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2004 |
text {* |
53750 | 2005 |
\noindent |
2006 |
Using the @{text "of"} keyword, different equations are specified for @{const |
|
2007 |
cont} depending on which constructor is selected. |
|
2008 |
||
2009 |
Here are more examples to conclude: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2010 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2011 |
|
53826 | 2012 |
primcorec |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2013 |
even_infty :: even_enat and |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2014 |
odd_infty :: odd_enat |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2015 |
where |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2016 |
"\<not> is_Even_EZero even_infty" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2017 |
"un_Even_ESuc even_infty = odd_infty" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2018 |
"un_Odd_ESuc odd_infty = even_infty" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2019 |
|
53752 | 2020 |
text {* \blankline *} |
2021 |
||
53826 | 2022 |
primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2023 |
"lbl\<^sub>i\<^sub>i (iterate\<^sub>i\<^sub>i f x) = x" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2024 |
"sub\<^sub>i\<^sub>i (iterate\<^sub>i\<^sub>i f x) = lmap (iterate\<^sub>i\<^sub>i f) (f x)" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2025 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2026 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2027 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2028 |
|
53750 | 2029 |
|
53617 | 2030 |
subsection {* Command Syntax |
2031 |
\label{ssec:primcorec-command-syntax} *} |
|
2032 |
||
2033 |
||
53826 | 2034 |
subsubsection {* \keyw{primcorec} and \keyw{primcorecursive} |
53753
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
2035 |
\label{sssec:primcorecursive-and-primcorec} *} |
52840 | 2036 |
|
2037 |
text {* |
|
53829 | 2038 |
\begin{matharray}{rcl} |
2039 |
@{command_def "primcorec"} & : & @{text "local_theory \<rightarrow> local_theory"} \\ |
|
2040 |
@{command_def "primcorecursive"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2041 |
\end{matharray} |
|
52840 | 2042 |
|
2043 |
@{rail " |
|
53829 | 2044 |
(@@{command primcorec} | @@{command primcorecursive}) target? \\ @{syntax pcr_option}? fixes @'where' |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2045 |
(@{syntax pcr_formula} + '|') |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2046 |
; |
53828 | 2047 |
@{syntax_def pcr_option}: '(' ('sequential' | 'exhaustive') ')' |
52840 | 2048 |
; |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2049 |
@{syntax_def pcr_formula}: thmdecl? prop (@'of' (term * ))? |
52840 | 2050 |
"} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2051 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2052 |
The optional target is optionally followed by a corecursion-specific option: |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2053 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2054 |
\begin{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2055 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2056 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2057 |
\item |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2058 |
The @{text "sequential"} option indicates that the conditions in specifications |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2059 |
expressed using the constructor or destructor view are to be interpreted |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2060 |
sequentially. |
53826 | 2061 |
|
2062 |
\item |
|
2063 |
The @{text "exhaustive"} option indicates that the conditions in specifications |
|
2064 |
expressed using the constructor or destructor view cover all possible cases. |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2065 |
\end{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2066 |
|
53826 | 2067 |
\noindent |
2068 |
The @{command primcorec} command is an abbreviation for @{command primcorecursive} with |
|
2069 |
@{text "by auto?"} to discharge any emerging proof obligations. |
|
52840 | 2070 |
*} |
52794 | 2071 |
|
52824 | 2072 |
|
53619 | 2073 |
(* |
52840 | 2074 |
subsection {* Generated Theorems |
2075 |
\label{ssec:primcorec-generated-theorems} *} |
|
53619 | 2076 |
*) |
52794 | 2077 |
|
2078 |
||
53623 | 2079 |
(* |
2080 |
subsection {* Recursive Default Values for Selectors |
|
2081 |
\label{ssec:primcorec-recursive-default-values-for-selectors} *} |
|
2082 |
||
2083 |
text {* |
|
2084 |
partial_function to the rescue |
|
2085 |
*} |
|
2086 |
*) |
|
2087 |
||
2088 |
||
52827 | 2089 |
section {* Registering Bounded Natural Functors |
52805 | 2090 |
\label{sec:registering-bounded-natural-functors} *} |
52792 | 2091 |
|
52805 | 2092 |
text {* |
53647 | 2093 |
The (co)datatype package can be set up to allow nested recursion through |
2094 |
arbitrary type constructors, as long as they adhere to the BNF requirements and |
|
2095 |
are registered as BNFs. |
|
52805 | 2096 |
*} |
2097 |
||
52824 | 2098 |
|
53619 | 2099 |
(* |
53617 | 2100 |
subsection {* Introductory Example |
2101 |
\label{ssec:bnf-introductory-example} *} |
|
52805 | 2102 |
|
2103 |
text {* |
|
2104 |
More examples in \verb|~~/src/HOL/BNF/Basic_BNFs.thy| and |
|
2105 |
\verb|~~/src/HOL/BNF/More_BNFs.thy|. |
|
52806 | 2106 |
|
53617 | 2107 |
%Mention distinction between live and dead type arguments; |
2108 |
% * and existence of map, set for those |
|
2109 |
%mention =>. |
|
52805 | 2110 |
*} |
53619 | 2111 |
*) |
52794 | 2112 |
|
52824 | 2113 |
|
53617 | 2114 |
subsection {* Command Syntax |
2115 |
\label{ssec:bnf-command-syntax} *} |
|
2116 |
||
2117 |
||
53621 | 2118 |
subsubsection {* \keyw{bnf} |
2119 |
\label{sssec:bnf} *} |
|
52794 | 2120 |
|
53028 | 2121 |
text {* |
53829 | 2122 |
\begin{matharray}{rcl} |
2123 |
@{command_def "bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2124 |
\end{matharray} |
|
2125 |
||
53028 | 2126 |
@{rail " |
53829 | 2127 |
@@{command bnf} target? (name ':')? term \\ |
53534 | 2128 |
term_list term term_list term? |
53028 | 2129 |
; |
53534 | 2130 |
X_list: '[' (X + ',') ']' |
53028 | 2131 |
"} |
2132 |
*} |
|
52805 | 2133 |
|
53617 | 2134 |
|
53621 | 2135 |
subsubsection {* \keyw{print\_bnfs} |
2136 |
\label{sssec:print-bnfs} *} |
|
53617 | 2137 |
|
2138 |
text {* |
|
53829 | 2139 |
\begin{matharray}{rcl} |
2140 |
@{command_def "print_bnfs"} & : & @{text "local_theory \<rightarrow>"} |
|
2141 |
\end{matharray} |
|
2142 |
||
53647 | 2143 |
@{rail " |
53829 | 2144 |
@@{command print_bnfs} |
53647 | 2145 |
"} |
53617 | 2146 |
*} |
2147 |
||
2148 |
||
2149 |
section {* Deriving Destructors and Theorems for Free Constructors |
|
2150 |
\label{sec:deriving-destructors-and-theorems-for-free-constructors} *} |
|
52794 | 2151 |
|
52805 | 2152 |
text {* |
53623 | 2153 |
The derivation of convenience theorems for types equipped with free constructors, |
53829 | 2154 |
as performed internally by @{command datatype_new} and @{command codatatype}, |
53623 | 2155 |
is available as a stand-alone command called @{command wrap_free_constructors}. |
52794 | 2156 |
|
53617 | 2157 |
% * need for this is rare but may arise if you want e.g. to add destructors to |
2158 |
% a type not introduced by ... |
|
2159 |
% |
|
2160 |
% * also useful for compatibility with old package, e.g. add destructors to |
|
2161 |
% old \keyw{datatype} |
|
2162 |
% |
|
2163 |
% * @{command wrap_free_constructors} |
|
53623 | 2164 |
% * @{text "no_discs_sels"}, @{text "rep_compat"} |
53617 | 2165 |
% * hack to have both co and nonco view via locale (cf. ext nats) |
52805 | 2166 |
*} |
52792 | 2167 |
|
52824 | 2168 |
|
53619 | 2169 |
(* |
53617 | 2170 |
subsection {* Introductory Example |
2171 |
\label{ssec:ctors-introductory-example} *} |
|
53619 | 2172 |
*) |
52794 | 2173 |
|
52824 | 2174 |
|
53617 | 2175 |
subsection {* Command Syntax |
2176 |
\label{ssec:ctors-command-syntax} *} |
|
2177 |
||
2178 |
||
53621 | 2179 |
subsubsection {* \keyw{wrap\_free\_constructors} |
53675 | 2180 |
\label{sssec:wrap-free-constructors} *} |
52828 | 2181 |
|
53018 | 2182 |
text {* |
53829 | 2183 |
\begin{matharray}{rcl} |
2184 |
@{command_def "wrap_free_constructors"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2185 |
\end{matharray} |
|
53018 | 2186 |
|
2187 |
@{rail " |
|
53829 | 2188 |
@@{command wrap_free_constructors} target? @{syntax dt_options} \\ |
53534 | 2189 |
term_list name @{syntax fc_discs_sels}? |
53018 | 2190 |
; |
53534 | 2191 |
@{syntax_def fc_discs_sels}: name_list (name_list_list name_term_list_list? )? |
53018 | 2192 |
; |
53534 | 2193 |
@{syntax_def name_term}: (name ':' term) |
53018 | 2194 |
"} |
2195 |
||
53617 | 2196 |
% options: no_discs_sels rep_compat |
53028 | 2197 |
|
53617 | 2198 |
% X_list is as for BNF |
53028 | 2199 |
|
53829 | 2200 |
\noindent |
53542 | 2201 |
Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems. |
53018 | 2202 |
*} |
52828 | 2203 |
|
52794 | 2204 |
|
53617 | 2205 |
(* |
52827 | 2206 |
section {* Standard ML Interface |
52805 | 2207 |
\label{sec:standard-ml-interface} *} |
52792 | 2208 |
|
52805 | 2209 |
text {* |
53623 | 2210 |
The package's programmatic interface. |
52805 | 2211 |
*} |
53617 | 2212 |
*) |
52794 | 2213 |
|
2214 |
||
53617 | 2215 |
(* |
52827 | 2216 |
section {* Interoperability |
52805 | 2217 |
\label{sec:interoperability} *} |
52794 | 2218 |
|
52805 | 2219 |
text {* |
53623 | 2220 |
The package's interaction with other Isabelle packages and tools, such as the |
2221 |
code generator and the counterexample generators. |
|
52805 | 2222 |
*} |
52794 | 2223 |
|
52824 | 2224 |
|
52828 | 2225 |
subsection {* Transfer and Lifting |
2226 |
\label{ssec:transfer-and-lifting} *} |
|
52794 | 2227 |
|
52824 | 2228 |
|
52828 | 2229 |
subsection {* Code Generator |
2230 |
\label{ssec:code-generator} *} |
|
52794 | 2231 |
|
52824 | 2232 |
|
52828 | 2233 |
subsection {* Quickcheck |
2234 |
\label{ssec:quickcheck} *} |
|
52794 | 2235 |
|
52824 | 2236 |
|
52828 | 2237 |
subsection {* Nitpick |
2238 |
\label{ssec:nitpick} *} |
|
52794 | 2239 |
|
52824 | 2240 |
|
52828 | 2241 |
subsection {* Nominal Isabelle |
2242 |
\label{ssec:nominal-isabelle} *} |
|
53617 | 2243 |
*) |
52794 | 2244 |
|
52805 | 2245 |
|
53617 | 2246 |
(* |
52827 | 2247 |
section {* Known Bugs and Limitations |
52805 | 2248 |
\label{sec:known-bugs-and-limitations} *} |
2249 |
||
2250 |
text {* |
|
53623 | 2251 |
Known open issues of the package. |
52805 | 2252 |
*} |
52794 | 2253 |
|
2254 |
text {* |
|
53753
ae7f50e70c09
renamed "primcorec" to "primcorecursive", to open the door to a 'theory -> theory' command called "primcorec" (cf. "fun" vs. "function")
blanchet
parents:
53752
diff
changeset
|
2255 |
%* primcorecursive and primcorec is unfinished |
53617 | 2256 |
% |
2257 |
%* slow n-ary mutual (co)datatype, avoid as much as possible (e.g. using nesting) |
|
2258 |
% |
|
2259 |
%* issues with HOL-Proofs? |
|
2260 |
% |
|
2261 |
%* partial documentation |
|
2262 |
% |
|
2263 |
%* no way to register "sum" and "prod" as (co)datatypes to enable N2M reduction for them |
|
2264 |
% (for @{command datatype_new_compat} and prim(co)rec) |
|
2265 |
% |
|
53619 | 2266 |
% * a fortiori, no way to register same type as both data- and codatatype |
53617 | 2267 |
% |
2268 |
%* no recursion through unused arguments (unlike with the old package) |
|
2269 |
% |
|
2270 |
%* in a locale, cannot use locally fixed types (because of limitation in typedef)? |
|
53619 | 2271 |
% |
2272 |
% *names of variables suboptimal |
|
52822 | 2273 |
*} |
53675 | 2274 |
*) |
52822 | 2275 |
|
2276 |
||
52827 | 2277 |
section {* Acknowledgments |
52822 | 2278 |
\label{sec:acknowledgments} *} |
2279 |
||
2280 |
text {* |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2281 |
Tobias Nipkow and Makarius Wenzel encouraged us to implement the new |
53617 | 2282 |
(co)datatype package. Andreas Lochbihler provided lots of comments on earlier |
2283 |
versions of the package, especially for the coinductive part. Brian Huffman |
|
2284 |
suggested major simplifications to the internal constructions, much of which has |
|
2285 |
yet to be implemented. Florian Haftmann and Christian Urban provided general |
|
53675 | 2286 |
advice on Isabelle and package writing. Stefan Milius and Lutz Schr\"oder |
53617 | 2287 |
suggested an elegant proof to eliminate one of the BNF assumptions. |
52794 | 2288 |
*} |
53617 | 2289 |
|
52792 | 2290 |
end |