author | blanchet |
Sun, 15 Sep 2013 23:02:23 +0200 | |
changeset 53643 | 673cb2c9d695 |
parent 53642 | 05ca82603671 |
child 53644 | eb8362530715 |
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 |
52792 | 12 |
begin |
13 |
||
52828 | 14 |
|
15 |
section {* Introduction |
|
16 |
\label{sec:introduction} *} |
|
52792 | 17 |
|
18 |
text {* |
|
53028 | 19 |
The 2013 edition of Isabelle introduced a new definitional package for freely |
20 |
generated datatypes and codatatypes. The datatype support is similar to that |
|
21 |
provided by the earlier package due to Berghofer and Wenzel |
|
22 |
\cite{Berghofer-Wenzel:1999:TPHOL}, documented in the Isar reference manual |
|
53535 | 23 |
\cite{isabelle-isar-ref}; indeed, replacing the keyword \keyw{datatype} by |
53028 | 24 |
@{command datatype_new} is usually all that is needed to port existing theories |
25 |
to use the new package. |
|
52840 | 26 |
|
52841 | 27 |
Perhaps the main advantage of the new package is that it supports recursion |
53619 | 28 |
through a large class of non-datatypes, such as finite sets: |
52792 | 29 |
*} |
30 |
||
53028 | 31 |
datatype_new 'a tree\<^sub>f\<^sub>s = Node\<^sub>f\<^sub>s 'a "'a tree\<^sub>f\<^sub>s fset" |
52792 | 32 |
|
33 |
text {* |
|
52794 | 34 |
\noindent |
53025 | 35 |
Another strong point is the support for local definitions: |
52792 | 36 |
*} |
37 |
||
52805 | 38 |
context linorder |
39 |
begin |
|
52841 | 40 |
datatype_new flag = Less | Eq | Greater |
52805 | 41 |
end |
52792 | 42 |
|
43 |
text {* |
|
52794 | 44 |
\noindent |
52840 | 45 |
The package also provides some convenience, notably automatically generated |
53543 | 46 |
discriminators and selectors. |
52794 | 47 |
|
53025 | 48 |
In addition to plain inductive datatypes, the new package supports coinductive |
52840 | 49 |
datatypes, or \emph{codatatypes}, which may have infinite values. For example, |
53028 | 50 |
the following command introduces the type of lazy lists, which comprises both |
51 |
finite and infinite values: |
|
52794 | 52 |
*} |
53 |
||
53623 | 54 |
(*<*) |
55 |
locale dummy_llist |
|
56 |
begin |
|
57 |
(*>*) |
|
58 |
codatatype 'a llist = LNil | LCons 'a "'a llist" |
|
52794 | 59 |
|
60 |
text {* |
|
61 |
\noindent |
|
52840 | 62 |
Mixed inductive--coinductive recursion is possible via nesting. Compare the |
53028 | 63 |
following four Rose tree examples: |
52794 | 64 |
*} |
65 |
||
53028 | 66 |
datatype_new 'a tree\<^sub>f\<^sub>f = Node\<^sub>f\<^sub>f 'a "'a tree\<^sub>f\<^sub>f list" |
67 |
datatype_new 'a tree\<^sub>f\<^sub>i = Node\<^sub>f\<^sub>i 'a "'a tree\<^sub>f\<^sub>i llist" |
|
68 |
codatatype 'a tree\<^sub>i\<^sub>f = Node\<^sub>i\<^sub>f 'a "'a tree\<^sub>i\<^sub>f list" |
|
69 |
codatatype 'a tree\<^sub>i\<^sub>i = Node\<^sub>i\<^sub>i 'a "'a tree\<^sub>i\<^sub>i llist" |
|
53025 | 70 |
(*<*) |
71 |
end |
|
72 |
(*>*) |
|
52792 | 73 |
|
52794 | 74 |
text {* |
52840 | 75 |
The first two tree types allow only finite branches, whereas the last two allow |
53028 | 76 |
branches of infinite length. Orthogonally, the nodes in the first and third |
77 |
types have finite branching, whereas those of the second and fourth may have |
|
78 |
infinitely many direct subtrees. |
|
52840 | 79 |
|
52794 | 80 |
To use the package, it is necessary to import the @{theory BNF} theory, which |
53552 | 81 |
can be precompiled into the \texttt{HOL-BNF} image. The following commands show |
52806 | 82 |
how to launch jEdit/PIDE with the image loaded and how to build the image |
83 |
without launching jEdit: |
|
52794 | 84 |
*} |
85 |
||
86 |
text {* |
|
87 |
\noindent |
|
52806 | 88 |
\ \ \ \ \texttt{isabelle jedit -l HOL-BNF} \\ |
52827 | 89 |
\noindent |
52828 | 90 |
\hbox{}\ \ \ \ \texttt{isabelle build -b HOL-BNF} |
52794 | 91 |
*} |
92 |
||
93 |
text {* |
|
52805 | 94 |
The package, like its predecessor, fully adheres to the LCF philosophy |
95 |
\cite{mgordon79}: The characteristic theorems associated with the specified |
|
96 |
(co)datatypes are derived rather than introduced axiomatically.% |
|
53543 | 97 |
\footnote{If the @{text quick_and_dirty} option is enabled, some of the |
52841 | 98 |
internal constructions and most of the internal proof obligations are skipped.} |
52805 | 99 |
The package's metatheory is described in a pair of papers |
53552 | 100 |
\cite{traytel-et-al-2012,blanchette-et-al-wit}. The central notion is that of a |
101 |
\emph{bounded natural functor} (BNF)---a well-behaved type constructor for which |
|
102 |
nested (co)recursion is supported. |
|
52792 | 103 |
|
52794 | 104 |
This tutorial is organized as follows: |
105 |
||
52805 | 106 |
\begin{itemize} |
52822 | 107 |
\setlength{\itemsep}{0pt} |
108 |
||
52805 | 109 |
\item Section \ref{sec:defining-datatypes}, ``Defining Datatypes,'' |
52822 | 110 |
describes how to specify datatypes using the @{command datatype_new} command. |
52805 | 111 |
|
53018 | 112 |
\item Section \ref{sec:defining-recursive-functions}, ``Defining Recursive |
52805 | 113 |
Functions,'' describes how to specify recursive functions using |
53535 | 114 |
@{command primrec_new}, \keyw{fun}, and \keyw{function}. |
52805 | 115 |
|
116 |
\item Section \ref{sec:defining-codatatypes}, ``Defining Codatatypes,'' |
|
52822 | 117 |
describes how to specify codatatypes using the @{command codatatype} command. |
52805 | 118 |
|
53018 | 119 |
\item Section \ref{sec:defining-corecursive-functions}, ``Defining Corecursive |
52805 | 120 |
Functions,'' describes how to specify corecursive functions using the |
53535 | 121 |
@{command primcorec} command. |
52794 | 122 |
|
53018 | 123 |
\item Section \ref{sec:registering-bounded-natural-functors}, ``Registering |
53552 | 124 |
Bounded Natural Functors,'' explains how to use the @{command bnf} command |
125 |
to register arbitrary type constructors as BNFs. |
|
52805 | 126 |
|
53552 | 127 |
\item Section |
53617 | 128 |
\ref{sec:deriving-destructors-and-theorems-for-free-constructors}, |
129 |
``Deriving Destructors and Theorems for Free Constructors,'' explains how to |
|
53552 | 130 |
use the command @{command wrap_free_constructors} to derive destructor constants |
131 |
and theorems for freely generated types, as performed internally by @{command |
|
132 |
datatype_new} and @{command codatatype}. |
|
52794 | 133 |
|
53617 | 134 |
%\item Section \ref{sec:standard-ml-interface}, ``Standard ML Interface,'' |
135 |
%describes the package's programmatic interface. |
|
52794 | 136 |
|
53617 | 137 |
%\item Section \ref{sec:interoperability}, ``Interoperability,'' |
138 |
%is concerned with the packages' interaction with other Isabelle packages and |
|
139 |
%tools, such as the code generator and the counterexample generators. |
|
52805 | 140 |
|
53617 | 141 |
%\item Section \ref{sec:known-bugs-and-limitations}, ``Known Bugs and |
142 |
%Limitations,'' concludes with known open issues at the time of writing. |
|
52805 | 143 |
\end{itemize} |
52822 | 144 |
|
145 |
||
146 |
\newbox\boxA |
|
147 |
\setbox\boxA=\hbox{\texttt{nospam}} |
|
148 |
||
149 |
\newcommand\authoremaili{\texttt{blan{\color{white}nospam}\kern-\wd\boxA{}chette@\allowbreak |
|
150 |
in.\allowbreak tum.\allowbreak de}} |
|
53028 | 151 |
\newcommand\authoremailii{\texttt{lore{\color{white}nospam}\kern-\wd\boxA{}nz.panny@\allowbreak |
152 |
\allowbreak tum.\allowbreak de}} |
|
153 |
\newcommand\authoremailiii{\texttt{pope{\color{white}nospam}\kern-\wd\boxA{}scua@\allowbreak |
|
52822 | 154 |
in.\allowbreak tum.\allowbreak de}} |
53028 | 155 |
\newcommand\authoremailiv{\texttt{tray{\color{white}nospam}\kern-\wd\boxA{}tel@\allowbreak |
52822 | 156 |
in.\allowbreak tum.\allowbreak de}} |
157 |
||
53028 | 158 |
The commands @{command datatype_new} and @{command primrec_new} are expected to |
53535 | 159 |
displace \keyw{datatype} and \keyw{primrec} in a future release. Authors of new |
160 |
theories are encouraged to use the new commands, and maintainers of older |
|
53028 | 161 |
theories may want to consider upgrading. |
52841 | 162 |
|
163 |
Comments and bug reports concerning either the tool or this tutorial should be |
|
53028 | 164 |
directed to the authors at \authoremaili, \authoremailii, \authoremailiii, |
165 |
and \authoremailiv. |
|
52822 | 166 |
|
167 |
\begin{framed} |
|
168 |
\noindent |
|
52841 | 169 |
\textbf{Warning:} This tutorial is under heavy construction. Please apologise |
53028 | 170 |
for its appearance. If you have ideas regarding material that should be |
171 |
included, please let the authors know. |
|
52822 | 172 |
\end{framed} |
52794 | 173 |
*} |
174 |
||
53491 | 175 |
|
52827 | 176 |
section {* Defining Datatypes |
52805 | 177 |
\label{sec:defining-datatypes} *} |
178 |
||
179 |
text {* |
|
53623 | 180 |
Datatypes can be specified using the @{command datatype_new} command. The |
181 |
command is first illustrated through concrete examples featuring different |
|
182 |
flavors of recursion. More examples can be found in the directory |
|
183 |
\verb|~~/src/HOL/BNF/Examples|. |
|
52805 | 184 |
*} |
52792 | 185 |
|
52824 | 186 |
|
53617 | 187 |
subsection {* Introductory Examples |
188 |
\label{ssec:datatype-introductory-examples} *} |
|
52794 | 189 |
|
53621 | 190 |
|
191 |
subsubsection {* Nonrecursive Types |
|
192 |
\label{sssec:datatype-nonrecursive-types} *} |
|
52794 | 193 |
|
52805 | 194 |
text {* |
53028 | 195 |
Datatypes are introduced by specifying the desired names and argument types for |
53491 | 196 |
their constructors. \emph{Enumeration} types are the simplest form of datatype. |
53028 | 197 |
All their constructors are nullary: |
52805 | 198 |
*} |
199 |
||
52828 | 200 |
datatype_new trool = Truue | Faalse | Perhaaps |
52805 | 201 |
|
202 |
text {* |
|
53028 | 203 |
\noindent |
53491 | 204 |
Here, @{const Truue}, @{const Faalse}, and @{const Perhaaps} have the type @{typ trool}. |
53028 | 205 |
|
206 |
Polymorphic types are possible, such as the following option type, modeled after |
|
207 |
its homologue from the @{theory Option} theory: |
|
52805 | 208 |
*} |
209 |
||
53025 | 210 |
(*<*) |
211 |
hide_const None Some |
|
212 |
(*>*) |
|
213 |
datatype_new 'a option = None | Some 'a |
|
52805 | 214 |
|
215 |
text {* |
|
53028 | 216 |
\noindent |
53491 | 217 |
The constructors are @{text "None :: 'a option"} and |
218 |
@{text "Some :: 'a \<Rightarrow> 'a option"}. |
|
53028 | 219 |
|
220 |
The next example has three type parameters: |
|
52805 | 221 |
*} |
222 |
||
223 |
datatype_new ('a, 'b, 'c) triple = Triple 'a 'b 'c |
|
224 |
||
53028 | 225 |
text {* |
226 |
\noindent |
|
227 |
The constructor is |
|
53491 | 228 |
@{text "Triple :: 'a \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> ('a, 'b, 'c) triple"}. |
53028 | 229 |
Unlike in Standard ML, curried constructors are supported. The uncurried variant |
230 |
is also possible: |
|
231 |
*} |
|
232 |
||
233 |
datatype_new ('a, 'b, 'c) triple\<^sub>u = Triple\<^sub>u "'a * 'b * 'c" |
|
234 |
||
52824 | 235 |
|
53621 | 236 |
subsubsection {* Simple Recursion |
237 |
\label{sssec:datatype-simple-recursion} *} |
|
52794 | 238 |
|
52805 | 239 |
text {* |
53491 | 240 |
Natural numbers are the simplest example of a recursive type: |
52805 | 241 |
*} |
242 |
||
53332 | 243 |
datatype_new nat = Zero | Suc nat |
52805 | 244 |
|
245 |
text {* |
|
53491 | 246 |
\noindent |
247 |
Lists were shown in the introduction. Terminated lists are a variant: |
|
52805 | 248 |
*} |
249 |
||
53491 | 250 |
(*<*) |
251 |
locale dummy_tlist |
|
252 |
begin |
|
253 |
(*>*) |
|
52805 | 254 |
datatype_new ('a, 'b) tlist = TNil 'b | TCons 'a "('a, 'b) tlist" |
53491 | 255 |
(*<*) |
256 |
end |
|
257 |
(*>*) |
|
52805 | 258 |
|
259 |
text {* |
|
53491 | 260 |
\noindent |
53552 | 261 |
Occurrences of nonatomic types on the right-hand side of the equal sign must be |
262 |
enclosed in double quotes, as is customary in Isabelle. |
|
52805 | 263 |
*} |
264 |
||
52824 | 265 |
|
53621 | 266 |
subsubsection {* Mutual Recursion |
267 |
\label{sssec:datatype-mutual-recursion} *} |
|
52794 | 268 |
|
52805 | 269 |
text {* |
53552 | 270 |
\emph{Mutually recursive} types are introduced simultaneously and may refer to |
271 |
each other. The example below introduces a pair of types for even and odd |
|
272 |
natural numbers: |
|
52805 | 273 |
*} |
274 |
||
53623 | 275 |
datatype_new even_nat = Even_Zero | Even_Suc odd_nat |
276 |
and odd_nat = Odd_Suc even_nat |
|
52805 | 277 |
|
278 |
text {* |
|
53491 | 279 |
\noindent |
280 |
Arithmetic expressions are defined via terms, terms via factors, and factors via |
|
281 |
expressions: |
|
52805 | 282 |
*} |
283 |
||
52841 | 284 |
datatype_new ('a, 'b) exp = |
285 |
Term "('a, 'b) trm" | Sum "('a, 'b) trm" "('a, 'b) exp" |
|
52805 | 286 |
and ('a, 'b) trm = |
52841 | 287 |
Factor "('a, 'b) fct" | Prod "('a, 'b) fct" "('a, 'b) trm" |
288 |
and ('a, 'b) fct = |
|
289 |
Const 'a | Var 'b | Expr "('a, 'b) exp" |
|
52805 | 290 |
|
52824 | 291 |
|
53621 | 292 |
subsubsection {* Nested Recursion |
293 |
\label{sssec:datatype-nested-recursion} *} |
|
52794 | 294 |
|
52805 | 295 |
text {* |
53491 | 296 |
\emph{Nested recursion} occurs when recursive occurrences of a type appear under |
297 |
a type constructor. The introduction showed some examples of trees with nesting |
|
298 |
through lists. A more complex example, that reuses our @{text option} type, |
|
299 |
follows: |
|
52805 | 300 |
*} |
301 |
||
52843 | 302 |
datatype_new 'a btree = |
53025 | 303 |
BNode 'a "'a btree option" "'a btree option" |
52805 | 304 |
|
305 |
text {* |
|
53491 | 306 |
\noindent |
307 |
Not all nestings are admissible. For example, this command will fail: |
|
52805 | 308 |
*} |
309 |
||
53491 | 310 |
datatype_new 'a wrong = Wrong (*<*)'a |
53542 | 311 |
typ (*>*)"'a wrong \<Rightarrow> 'a" |
52806 | 312 |
|
313 |
text {* |
|
53491 | 314 |
\noindent |
315 |
The issue is that the function arrow @{text "\<Rightarrow>"} allows recursion |
|
316 |
only through its right-hand side. This issue is inherited by polymorphic |
|
317 |
datatypes defined in terms of~@{text "\<Rightarrow>"}: |
|
318 |
*} |
|
319 |
||
320 |
datatype_new ('a, 'b) fn = Fn "'a \<Rightarrow> 'b" |
|
321 |
datatype_new 'a also_wrong = Also_Wrong (*<*)'a |
|
53542 | 322 |
typ (*>*)"('a also_wrong, 'a) fn" |
53491 | 323 |
|
324 |
text {* |
|
325 |
\noindent |
|
53621 | 326 |
This is legal: |
327 |
*} |
|
328 |
||
329 |
datatype_new 'a ftree = FTLeaf 'a | FTNode "'a \<Rightarrow> 'a ftree" |
|
330 |
||
331 |
text {* |
|
332 |
\noindent |
|
53491 | 333 |
In general, type constructors @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
334 |
allow recursion on a subset of their type arguments @{text 'a\<^sub>1}, \ldots, |
|
335 |
@{text 'a\<^sub>m}. These type arguments are called \emph{live}; the remaining |
|
336 |
type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and |
|
337 |
@{typ "('a, 'b) fn"}, the type variable @{typ 'a} is dead and @{typ 'b} is live. |
|
53552 | 338 |
|
339 |
Type constructors must be registered as bounded natural functors (BNFs) to have |
|
340 |
live arguments. This is done automatically for datatypes and codatatypes |
|
341 |
introduced by the @{command datatype_new} and @{command codatatype} commands. |
|
342 |
Section~\ref{sec:registering-bounded-natural-functors} explains how to register |
|
343 |
arbitrary type constructors as BNFs. |
|
52806 | 344 |
*} |
345 |
||
346 |
||
53621 | 347 |
subsubsection {* Custom Names and Syntaxes |
348 |
\label{sssec:datatype-custom-names-and-syntaxes} *} |
|
52805 | 349 |
|
350 |
text {* |
|
53491 | 351 |
The @{command datatype_new} command introduces various constants in addition to |
53617 | 352 |
the constructors. With each datatype are associated set functions, a map |
353 |
function, a relator, discriminators, and selectors, all of which can be given |
|
354 |
custom names. In the example below, the traditional names |
|
355 |
@{text set}, @{text map}, @{text list_all2}, @{text null}, @{text hd}, and |
|
356 |
@{text tl} override the default names @{text list_set}, @{text list_map}, @{text |
|
357 |
list_rel}, @{text is_Nil}, @{text un_Cons1}, and @{text un_Cons2}: |
|
52822 | 358 |
*} |
359 |
||
52841 | 360 |
(*<*) |
361 |
no_translations |
|
362 |
"[x, xs]" == "x # [xs]" |
|
363 |
"[x]" == "x # []" |
|
364 |
||
365 |
no_notation |
|
366 |
Nil ("[]") and |
|
367 |
Cons (infixr "#" 65) |
|
368 |
||
53543 | 369 |
hide_type list |
53544 | 370 |
hide_const Nil Cons hd tl set map list_all2 list_case list_rec |
53025 | 371 |
|
372 |
locale dummy_list |
|
373 |
begin |
|
52841 | 374 |
(*>*) |
53025 | 375 |
datatype_new (set: 'a) list (map: map rel: list_all2) = |
52822 | 376 |
null: Nil (defaults tl: Nil) |
53025 | 377 |
| Cons (hd: 'a) (tl: "'a list") |
52822 | 378 |
|
379 |
text {* |
|
380 |
\noindent |
|
381 |
The command introduces a discriminator @{const null} and a pair of selectors |
|
382 |
@{const hd} and @{const tl} characterized as follows: |
|
383 |
% |
|
53025 | 384 |
\[@{thm list.collapse(1)[of xs, no_vars]} |
385 |
\qquad @{thm list.collapse(2)[of xs, no_vars]}\] |
|
52822 | 386 |
% |
387 |
For two-constructor datatypes, a single discriminator constant suffices. The |
|
53491 | 388 |
discriminator associated with @{const Cons} is simply |
389 |
@{term "\<lambda>xs. \<not> null xs"}. |
|
52822 | 390 |
|
53553 | 391 |
The @{text defaults} clause following the @{const Nil} constructor specifies a |
392 |
default value for selectors associated with other constructors. Here, it is used |
|
393 |
to ensure that the tail of the empty list is itself (instead of being left |
|
53535 | 394 |
unspecified). |
52822 | 395 |
|
53617 | 396 |
Because @{const Nil} is nullary, it is also possible to use |
53491 | 397 |
@{term "\<lambda>xs. xs = Nil"} as a discriminator. This is specified by |
53534 | 398 |
entering ``@{text "="}'' instead of the identifier @{const null}. Although this |
53535 | 399 |
may look appealing, the mixture of constructors and selectors in the |
53534 | 400 |
characteristic theorems can lead Isabelle's automation to switch between the |
401 |
constructor and the destructor view in surprising ways. |
|
52822 | 402 |
|
53491 | 403 |
The usual mixfix syntaxes are available for both types and constructors. For |
404 |
example: |
|
52805 | 405 |
*} |
52794 | 406 |
|
53025 | 407 |
(*<*) |
408 |
end |
|
409 |
(*>*) |
|
53552 | 410 |
datatype_new ('a, 'b) prod (infixr "*" 20) = Pair 'a 'b |
411 |
||
412 |
text {* \blankline *} |
|
52822 | 413 |
|
52841 | 414 |
datatype_new (set: 'a) list (map: map rel: list_all2) = |
52822 | 415 |
null: Nil ("[]") |
52841 | 416 |
| Cons (hd: 'a) (tl: "'a list") (infixr "#" 65) |
417 |
||
418 |
text {* |
|
53535 | 419 |
\noindent |
53025 | 420 |
Incidentally, this is how the traditional syntaxes can be set up: |
52841 | 421 |
*} |
422 |
||
423 |
syntax "_list" :: "args \<Rightarrow> 'a list" ("[(_)]") |
|
424 |
||
53552 | 425 |
text {* \blankline *} |
426 |
||
52841 | 427 |
translations |
428 |
"[x, xs]" == "x # [xs]" |
|
429 |
"[x]" == "x # []" |
|
52822 | 430 |
|
52824 | 431 |
|
53617 | 432 |
subsection {* Command Syntax |
433 |
\label{ssec:datatype-command-syntax} *} |
|
434 |
||
435 |
||
53621 | 436 |
subsubsection {* \keyw{datatype\_new} |
437 |
\label{sssec:datatype-new} *} |
|
52794 | 438 |
|
52822 | 439 |
text {* |
440 |
Datatype definitions have the following general syntax: |
|
441 |
||
52824 | 442 |
@{rail " |
53534 | 443 |
@@{command_def datatype_new} target? @{syntax dt_options}? \\ |
52824 | 444 |
(@{syntax dt_name} '=' (@{syntax ctor} + '|') + @'and') |
52828 | 445 |
; |
53623 | 446 |
@{syntax_def dt_options}: '(' (('no_discs_sels' | 'rep_compat') + ',') ')' |
52824 | 447 |
"} |
448 |
||
53534 | 449 |
The syntactic quantity \synt{target} can be used to specify a local |
450 |
context---e.g., @{text "(in linorder)"}. It is documented in the Isar reference |
|
451 |
manual \cite{isabelle-isar-ref}. |
|
452 |
% |
|
453 |
The optional target is optionally followed by datatype-specific options: |
|
52822 | 454 |
|
52824 | 455 |
\begin{itemize} |
456 |
\setlength{\itemsep}{0pt} |
|
457 |
||
458 |
\item |
|
53623 | 459 |
The @{text "no_discs_sels"} option indicates that no discriminators or selectors |
53543 | 460 |
should be generated. |
52822 | 461 |
|
52824 | 462 |
\item |
53623 | 463 |
The @{text "rep_compat"} option indicates that the names generated by the |
53534 | 464 |
package should contain optional (and normally not displayed) ``@{text "new."}'' |
53543 | 465 |
components to prevent clashes with a later call to \keyw{rep\_datatype}. See |
52824 | 466 |
Section~\ref{ssec:datatype-compatibility-issues} for details. |
467 |
\end{itemize} |
|
52822 | 468 |
|
52827 | 469 |
The left-hand sides of the datatype equations specify the name of the type to |
53534 | 470 |
define, its type parameters, and additional information: |
52822 | 471 |
|
52824 | 472 |
@{rail " |
53534 | 473 |
@{syntax_def dt_name}: @{syntax tyargs}? name @{syntax map_rel}? mixfix? |
52824 | 474 |
; |
53534 | 475 |
@{syntax_def tyargs}: typefree | '(' ((name ':')? typefree + ',') ')' |
52824 | 476 |
; |
53534 | 477 |
@{syntax_def map_rel}: '(' ((('map' | 'rel') ':' name) +) ')' |
52824 | 478 |
"} |
52822 | 479 |
|
52827 | 480 |
\noindent |
53534 | 481 |
The syntactic quantity \synt{name} denotes an identifier, \synt{typefree} |
482 |
denotes fixed type variable (@{typ 'a}, @{typ 'b}, \ldots), and \synt{mixfix} |
|
483 |
denotes the usual parenthesized mixfix notation. They are documented in the Isar |
|
484 |
reference manual \cite{isabelle-isar-ref}. |
|
52822 | 485 |
|
52827 | 486 |
The optional names preceding the type variables allow to override the default |
487 |
names of the set functions (@{text t_set1}, \ldots, @{text t_setM}). |
|
488 |
Inside a mutually recursive datatype specification, all defined datatypes must |
|
489 |
specify exactly the same type variables in the same order. |
|
52822 | 490 |
|
52824 | 491 |
@{rail " |
53534 | 492 |
@{syntax_def ctor}: (name ':')? name (@{syntax ctor_arg} * ) \\ |
493 |
@{syntax dt_sel_defaults}? mixfix? |
|
52824 | 494 |
"} |
495 |
||
53535 | 496 |
\medskip |
497 |
||
52827 | 498 |
\noindent |
499 |
The main constituents of a constructor specification is the name of the |
|
500 |
constructor and the list of its argument types. An optional discriminator name |
|
53554 | 501 |
can be supplied at the front to override the default name |
502 |
(@{text t.is_C\<^sub>j}). |
|
52822 | 503 |
|
52824 | 504 |
@{rail " |
53534 | 505 |
@{syntax_def ctor_arg}: type | '(' name ':' type ')' |
52827 | 506 |
"} |
507 |
||
53535 | 508 |
\medskip |
509 |
||
52827 | 510 |
\noindent |
511 |
In addition to the type of a constructor argument, it is possible to specify a |
|
512 |
name for the corresponding selector to override the default name |
|
53554 | 513 |
(@{text un_C\<^sub>ji}). The same selector names can be reused for several |
514 |
constructors as long as they share the same type. |
|
52827 | 515 |
|
516 |
@{rail " |
|
53621 | 517 |
@{syntax_def dt_sel_defaults}: '(' 'defaults' (name ':' term +) ')' |
52824 | 518 |
"} |
52827 | 519 |
|
520 |
\noindent |
|
521 |
Given a constructor |
|
522 |
@{text "C \<Colon> \<sigma>\<^sub>1 \<Rightarrow> \<dots> \<Rightarrow> \<sigma>\<^sub>p \<Rightarrow> \<sigma>"}, |
|
523 |
default values can be specified for any selector |
|
524 |
@{text "un_D \<Colon> \<sigma> \<Rightarrow> \<tau>"} |
|
53535 | 525 |
associated with other constructors. The specified default value must be of type |
52828 | 526 |
@{text "\<sigma>\<^sub>1 \<Rightarrow> \<dots> \<Rightarrow> \<sigma>\<^sub>p \<Rightarrow> \<tau>"} |
53535 | 527 |
(i.e., it may depends on @{text C}'s arguments). |
52822 | 528 |
*} |
529 |
||
53617 | 530 |
|
53621 | 531 |
subsubsection {* \keyw{datatype\_new\_compat} |
532 |
\label{sssec:datatype-new-compat} *} |
|
53617 | 533 |
|
534 |
text {* |
|
53621 | 535 |
The old datatype package provides some functionality that is not yet replicated |
536 |
in the new package: |
|
537 |
||
538 |
\begin{itemize} |
|
539 |
\item It is integrated with \keyw{fun} and \keyw{function} |
|
540 |
\cite{isabelle-function}, Nitpick \cite{isabelle-nitpick}, Quickcheck, |
|
541 |
and other packages. |
|
542 |
||
543 |
\item It is extended by various add-ons, notably to produce instances of the |
|
544 |
@{const size} function. |
|
545 |
\end{itemize} |
|
546 |
||
547 |
\noindent |
|
548 |
New-style datatypes can in most case be registered as old-style datatypes using |
|
549 |
the command |
|
550 |
||
53617 | 551 |
@{rail " |
53621 | 552 |
@@{command_def datatype_new_compat} names |
53617 | 553 |
"} |
53621 | 554 |
|
555 |
\noindent |
|
556 |
where the \textit{names} argument is simply a space-separated list of type names |
|
557 |
that are mutually recursive. For example: |
|
558 |
*} |
|
559 |
||
53623 | 560 |
datatype_new_compat even_nat odd_nat |
53621 | 561 |
|
562 |
text {* \blankline *} |
|
563 |
||
53623 | 564 |
thm even_nat_odd_nat.size |
53621 | 565 |
|
566 |
text {* \blankline *} |
|
567 |
||
53623 | 568 |
ML {* Datatype_Data.get_info @{theory} @{type_name even_nat} *} |
53621 | 569 |
|
570 |
text {* |
|
571 |
For nested recursive datatypes, all types through which recursion takes place |
|
572 |
must be new-style datatypes. In principle, it should be possible to support |
|
573 |
old-style datatypes as well, but the command does not support this yet. |
|
53617 | 574 |
*} |
575 |
||
576 |
||
577 |
subsection {* Generated Constants |
|
578 |
\label{ssec:datatype-generated-constants} *} |
|
579 |
||
580 |
text {* |
|
53623 | 581 |
Given a datatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
53617 | 582 |
with $m > 0$ live type variables and $n$ constructors |
583 |
@{text "t.C\<^sub>1"}, \ldots, @{text "t.C\<^sub>n"}, the |
|
584 |
following auxiliary constants are introduced: |
|
585 |
||
586 |
\begin{itemize} |
|
587 |
\setlength{\itemsep}{0pt} |
|
588 |
||
589 |
\item \relax{Case combinator}: @{text t_case} (rendered using the familiar |
|
590 |
@{text case}--@{text of} syntax) |
|
591 |
||
592 |
\item \relax{Discriminators}: @{text "t.is_C\<^sub>1"}, \ldots, |
|
593 |
@{text "t.is_C\<^sub>n"} |
|
594 |
||
595 |
\item \relax{Selectors}: |
|
596 |
@{text t.un_C\<^sub>11}$, \ldots, @{text t.un_C\<^sub>1k\<^sub>1}, \\ |
|
597 |
\phantom{\relax{Selectors:}} \quad\vdots \\ |
|
598 |
\phantom{\relax{Selectors:}} @{text t.un_C\<^sub>n1}$, \ldots, @{text t.un_C\<^sub>nk\<^sub>n}. |
|
599 |
||
600 |
\item \relax{Set functions} (or \relax{natural transformations}): |
|
601 |
@{text t_set1}, \ldots, @{text t_setm} |
|
602 |
||
603 |
\item \relax{Map function} (or \relax{functorial action}): @{text t_map} |
|
604 |
||
605 |
\item \relax{Relator}: @{text t_rel} |
|
606 |
||
607 |
\item \relax{Iterator}: @{text t_fold} |
|
608 |
||
609 |
\item \relax{Recursor}: @{text t_rec} |
|
610 |
||
611 |
\end{itemize} |
|
612 |
||
613 |
\noindent |
|
614 |
The case combinator, discriminators, and selectors are collectively called |
|
615 |
\emph{destructors}. The prefix ``@{text "t."}'' is an optional component of the |
|
616 |
name and is normally hidden. |
|
617 |
*} |
|
618 |
||
619 |
||
52840 | 620 |
subsection {* Generated Theorems |
621 |
\label{ssec:datatype-generated-theorems} *} |
|
52828 | 622 |
|
623 |
text {* |
|
53544 | 624 |
The characteristic theorems generated by @{command datatype_new} are grouped in |
53623 | 625 |
three broad categories: |
53535 | 626 |
|
53543 | 627 |
\begin{itemize} |
628 |
\item The \emph{free constructor theorems} are properties about the constructors |
|
629 |
and destructors that can be derived for any freely generated type. Internally, |
|
53542 | 630 |
the derivation is performed by @{command wrap_free_constructors}. |
53535 | 631 |
|
53552 | 632 |
\item The \emph{functorial theorems} are properties of datatypes related to |
633 |
their BNF nature. |
|
634 |
||
635 |
\item The \emph{inductive theorems} are properties of datatypes related to |
|
53544 | 636 |
their inductive nature. |
53552 | 637 |
|
53543 | 638 |
\end{itemize} |
53535 | 639 |
|
640 |
\noindent |
|
53542 | 641 |
The full list of named theorems can be obtained as usual by entering the |
53543 | 642 |
command \keyw{print\_theorems} immediately after the datatype definition. |
53542 | 643 |
This list normally excludes low-level theorems that reveal internal |
53552 | 644 |
constructions. To make these accessible, add the line |
53542 | 645 |
*} |
53535 | 646 |
|
53542 | 647 |
declare [[bnf_note_all]] |
648 |
(*<*) |
|
649 |
declare [[bnf_note_all = false]] |
|
650 |
(*>*) |
|
53535 | 651 |
|
53552 | 652 |
text {* |
653 |
\noindent |
|
654 |
to the top of the theory file. |
|
655 |
*} |
|
53535 | 656 |
|
53621 | 657 |
subsubsection {* Free Constructor Theorems |
658 |
\label{sssec:free-constructor-theorems} *} |
|
53535 | 659 |
|
53543 | 660 |
(*<*) |
661 |
consts is_Cons :: 'a |
|
662 |
(*>*) |
|
663 |
||
53535 | 664 |
text {* |
53543 | 665 |
The first subgroup of properties are concerned with the constructors. |
666 |
They are listed below for @{typ "'a list"}: |
|
667 |
||
53552 | 668 |
\begin{indentblock} |
53543 | 669 |
\begin{description} |
53544 | 670 |
|
53642 | 671 |
\item[@{text "t."}\hthm{inject} @{text "[iff, induct_simp]"}\rm:] ~ \\ |
53544 | 672 |
@{thm list.inject[no_vars]} |
673 |
||
53642 | 674 |
\item[@{text "t."}\hthm{distinct} @{text "[simp, induct_simp]"}\rm:] ~ \\ |
53543 | 675 |
@{thm list.distinct(1)[no_vars]} \\ |
676 |
@{thm list.distinct(2)[no_vars]} |
|
677 |
||
53642 | 678 |
\item[@{text "t."}\hthm{exhaust} @{text "[cases t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 679 |
@{thm list.exhaust[no_vars]} |
680 |
||
53642 | 681 |
\item[@{text "t."}\hthm{nchotomy}\rm:] ~ \\ |
53543 | 682 |
@{thm list.nchotomy[no_vars]} |
683 |
||
684 |
\end{description} |
|
53552 | 685 |
\end{indentblock} |
53543 | 686 |
|
687 |
\noindent |
|
53621 | 688 |
In addition, these nameless theorems are registered as safe elimination rules: |
689 |
||
690 |
\begin{indentblock} |
|
691 |
\begin{description} |
|
692 |
||
53642 | 693 |
\item[@{text "t."}\hthm{list.distinct {\upshape[}THEN notE}@{text ", elim!"}\hthm{\upshape]}\rm:] ~ \\ |
53621 | 694 |
@{thm list.distinct(1)[THEN notE, elim!, no_vars]} \\ |
695 |
@{thm list.distinct(2)[THEN notE, elim!, no_vars]} |
|
696 |
||
697 |
\end{description} |
|
698 |
\end{indentblock} |
|
699 |
||
700 |
\noindent |
|
53543 | 701 |
The next subgroup is concerned with the case combinator: |
702 |
||
53552 | 703 |
\begin{indentblock} |
53543 | 704 |
\begin{description} |
53544 | 705 |
|
53642 | 706 |
\item[@{text "t."}\hthm{case} @{text "[simp]"}\rm:] ~ \\ |
53543 | 707 |
@{thm list.case(1)[no_vars]} \\ |
708 |
@{thm list.case(2)[no_vars]} |
|
709 |
||
53642 | 710 |
\item[@{text "t."}\hthm{case\_cong}\rm:] ~ \\ |
53543 | 711 |
@{thm list.case_cong[no_vars]} |
712 |
||
53642 | 713 |
\item[@{text "t."}\hthm{weak\_case\_cong} @{text "[cong]"}\rm:] ~ \\ |
53543 | 714 |
@{thm list.weak_case_cong[no_vars]} |
715 |
||
53642 | 716 |
\item[@{text "t."}\hthm{split}\rm:] ~ \\ |
53543 | 717 |
@{thm list.split[no_vars]} |
718 |
||
53642 | 719 |
\item[@{text "t."}\hthm{split\_asm}\rm:] ~ \\ |
53543 | 720 |
@{thm list.split_asm[no_vars]} |
721 |
||
53544 | 722 |
\item[@{text "t."}\hthm{splits} = @{text "split split_asm"}] |
53543 | 723 |
|
724 |
\end{description} |
|
53552 | 725 |
\end{indentblock} |
53543 | 726 |
|
727 |
\noindent |
|
728 |
The third and last subgroup revolves around discriminators and selectors: |
|
729 |
||
53552 | 730 |
\begin{indentblock} |
53543 | 731 |
\begin{description} |
53544 | 732 |
|
53642 | 733 |
\item[@{text "t."}\hthm{discs} @{text "[simp]"}\rm:] ~ \\ |
53543 | 734 |
@{thm list.discs(1)[no_vars]} \\ |
735 |
@{thm list.discs(2)[no_vars]} |
|
736 |
||
53642 | 737 |
\item[@{text "t."}\hthm{sels} @{text "[simp]"}\rm:] ~ \\ |
53543 | 738 |
@{thm list.sels(1)[no_vars]} \\ |
739 |
@{thm list.sels(2)[no_vars]} |
|
740 |
||
53642 | 741 |
\item[@{text "t."}\hthm{collapse} @{text "[simp]"}\rm:] ~ \\ |
53543 | 742 |
@{thm list.collapse(1)[no_vars]} \\ |
743 |
@{thm list.collapse(2)[no_vars]} |
|
744 |
||
53642 | 745 |
\item[@{text "t."}\hthm{disc\_exclude}\rm:] ~ \\ |
53543 | 746 |
These properties are missing for @{typ "'a list"} because there is only one |
747 |
proper discriminator. Had the datatype been introduced with a second |
|
53544 | 748 |
discriminator called @{const is_Cons}, they would have read thusly: \\[\jot] |
53543 | 749 |
@{prop "null list \<Longrightarrow> \<not> is_Cons list"} \\ |
750 |
@{prop "is_Cons list \<Longrightarrow> \<not> null list"} |
|
751 |
||
53642 | 752 |
\item[@{text "t."}\hthm{disc\_exhaust} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 753 |
@{thm list.disc_exhaust[no_vars]} |
754 |
||
53642 | 755 |
\item[@{text "t."}\hthm{expand}\rm:] ~ \\ |
53543 | 756 |
@{thm list.expand[no_vars]} |
757 |
||
53642 | 758 |
\item[@{text "t."}\hthm{case\_conv}\rm:] ~ \\ |
53543 | 759 |
@{thm list.case_conv[no_vars]} |
760 |
||
761 |
\end{description} |
|
53552 | 762 |
\end{indentblock} |
763 |
*} |
|
764 |
||
765 |
||
53621 | 766 |
subsubsection {* Functorial Theorems |
767 |
\label{sssec:functorial-theorems} *} |
|
53552 | 768 |
|
769 |
text {* |
|
53623 | 770 |
The BNF-related theorem are as follows: |
53552 | 771 |
|
772 |
\begin{indentblock} |
|
773 |
\begin{description} |
|
774 |
||
53642 | 775 |
\item[@{text "t."}\hthm{sets} @{text "[code]"}\rm:] ~ \\ |
53552 | 776 |
@{thm list.sets(1)[no_vars]} \\ |
777 |
@{thm list.sets(2)[no_vars]} |
|
778 |
||
53642 | 779 |
\item[@{text "t."}\hthm{map} @{text "[code]"}\rm:] ~ \\ |
53552 | 780 |
@{thm list.map(1)[no_vars]} \\ |
781 |
@{thm list.map(2)[no_vars]} |
|
782 |
||
53642 | 783 |
\item[@{text "t."}\hthm{rel\_inject} @{text "[code]"}\rm:] ~ \\ |
53552 | 784 |
@{thm list.rel_inject(1)[no_vars]} \\ |
785 |
@{thm list.rel_inject(2)[no_vars]} |
|
786 |
||
53642 | 787 |
\item[@{text "t."}\hthm{rel\_distinct} @{text "[code]"}\rm:] ~ \\ |
53552 | 788 |
@{thm list.rel_distinct(1)[no_vars]} \\ |
789 |
@{thm list.rel_distinct(2)[no_vars]} |
|
790 |
||
791 |
\end{description} |
|
792 |
\end{indentblock} |
|
53535 | 793 |
*} |
794 |
||
795 |
||
53621 | 796 |
subsubsection {* Inductive Theorems |
797 |
\label{sssec:inductive-theorems} *} |
|
53535 | 798 |
|
799 |
text {* |
|
53623 | 800 |
The inductive theorems are as follows: |
53544 | 801 |
|
53552 | 802 |
\begin{indentblock} |
53544 | 803 |
\begin{description} |
804 |
||
53642 | 805 |
\item[@{text "t."}\hthm{induct} @{text "[induct t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53544 | 806 |
@{thm list.induct[no_vars]} |
807 |
||
53642 | 808 |
\item[@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53544 | 809 |
Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
810 |
prove $m$ properties simultaneously. |
|
52828 | 811 |
|
53642 | 812 |
\item[@{text "t."}\hthm{fold} @{text "[code]"}\rm:] ~ \\ |
53544 | 813 |
@{thm list.fold(1)[no_vars]} \\ |
814 |
@{thm list.fold(2)[no_vars]} |
|
815 |
||
53642 | 816 |
\item[@{text "t."}\hthm{rec} @{text "[code]"}\rm:] ~ \\ |
53544 | 817 |
@{thm list.rec(1)[no_vars]} \\ |
818 |
@{thm list.rec(2)[no_vars]} |
|
819 |
||
820 |
\end{description} |
|
53552 | 821 |
\end{indentblock} |
53544 | 822 |
|
823 |
\noindent |
|
824 |
For convenience, @{command datatype_new} also provides the following collection: |
|
825 |
||
53552 | 826 |
\begin{indentblock} |
53544 | 827 |
\begin{description} |
828 |
||
829 |
\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}] ~ \\ |
|
830 |
@{text t.rel_distinct} @{text t.sets} |
|
831 |
||
832 |
\end{description} |
|
53552 | 833 |
\end{indentblock} |
52828 | 834 |
*} |
835 |
||
52794 | 836 |
|
53617 | 837 |
(* |
52827 | 838 |
subsection {* Compatibility Issues |
52824 | 839 |
\label{ssec:datatype-compatibility-issues} *} |
52794 | 840 |
|
52828 | 841 |
text {* |
53617 | 842 |
% * main incompabilities between two packages |
843 |
% * differences in theorem names (e.g. singular vs. plural for some props?) |
|
844 |
% * differences in "simps"? |
|
845 |
% * different recursor/induction in nested case |
|
846 |
% * discussed in Section~\ref{sec:defining-recursive-functions} |
|
847 |
% * different ML interfaces / extension mechanisms |
|
848 |
% |
|
849 |
% * register new datatype as old datatype |
|
850 |
% * motivation: |
|
851 |
% * do recursion through new datatype in old datatype |
|
852 |
% (e.g. useful when porting to the new package one type at a time) |
|
853 |
% * use old primrec |
|
854 |
% * use fun |
|
855 |
% * use extensions like size (needed for fun), the AFP order, Quickcheck, |
|
856 |
% Nitpick |
|
857 |
% * provide exactly the same theorems with the same names (compatibility) |
|
858 |
% * option 1 |
|
53623 | 859 |
% * @{text "rep_compat"} |
53617 | 860 |
% * \keyw{rep\_datatype} |
861 |
% * has some limitations |
|
862 |
% * mutually recursive datatypes? (fails with rep_datatype?) |
|
863 |
% * nested datatypes? (fails with datatype_new?) |
|
864 |
% * option 2 |
|
865 |
% * @{command datatype_new_compat} |
|
866 |
% * not fully implemented yet? |
|
52828 | 867 |
|
53617 | 868 |
% * register old datatype as new datatype |
869 |
% * no clean way yet |
|
870 |
% * if the goal is to do recursion through old datatypes, can register it as |
|
871 |
% a BNF (Section XXX) |
|
872 |
% * can also derive destructors etc. using @{command wrap_free_constructors} |
|
873 |
% (Section XXX) |
|
52828 | 874 |
*} |
53617 | 875 |
*) |
52828 | 876 |
|
52792 | 877 |
|
52827 | 878 |
section {* Defining Recursive Functions |
52805 | 879 |
\label{sec:defining-recursive-functions} *} |
880 |
||
881 |
text {* |
|
53535 | 882 |
This describes how to specify recursive functions over datatypes specified using |
883 |
@{command datatype_new}. The focus in on the @{command primrec_new} command, |
|
53621 | 884 |
which supports primitive recursion. More examples can be found in |
885 |
\verb|~~/src/HOL/BNF/Examples|. |
|
52828 | 886 |
|
53621 | 887 |
%%% TODO: partial_function |
52805 | 888 |
*} |
52792 | 889 |
|
52805 | 890 |
|
53617 | 891 |
subsection {* Introductory Examples |
892 |
\label{ssec:primrec-introductory-examples} *} |
|
52828 | 893 |
|
53621 | 894 |
|
895 |
subsubsection {* Nonrecursive Types |
|
896 |
\label{sssec:primrec-nonrecursive-types} *} |
|
52828 | 897 |
|
52841 | 898 |
text {* |
53621 | 899 |
Primitive recursion removes one layer of constructors on the left-hand side in |
900 |
each equation. For example: |
|
52841 | 901 |
*} |
902 |
||
903 |
primrec_new bool_of_trool :: "trool \<Rightarrow> bool" where |
|
53621 | 904 |
"bool_of_trool Faalse \<longleftrightarrow> False" | |
905 |
"bool_of_trool Truue \<longleftrightarrow> True" |
|
52841 | 906 |
|
53621 | 907 |
text {* \blankline *} |
52841 | 908 |
|
53025 | 909 |
primrec_new the_list :: "'a option \<Rightarrow> 'a list" where |
910 |
"the_list None = []" | |
|
911 |
"the_list (Some a) = [a]" |
|
52841 | 912 |
|
53621 | 913 |
text {* \blankline *} |
914 |
||
53025 | 915 |
primrec_new the_default :: "'a \<Rightarrow> 'a option \<Rightarrow> 'a" where |
916 |
"the_default d None = d" | |
|
917 |
"the_default _ (Some a) = a" |
|
52843 | 918 |
|
53621 | 919 |
text {* \blankline *} |
920 |
||
52841 | 921 |
primrec_new mirrror :: "('a, 'b, 'c) triple \<Rightarrow> ('c, 'b, 'a) triple" where |
922 |
"mirrror (Triple a b c) = Triple c b a" |
|
923 |
||
53621 | 924 |
text {* |
925 |
\noindent |
|
926 |
The equations can be specified in any order, and it is acceptable to leave out |
|
927 |
some cases, which are then unspecified. Pattern matching on the left-hand side |
|
928 |
is restricted to a single datatype, which must correspond to the same argument |
|
929 |
in all equations. |
|
930 |
*} |
|
52828 | 931 |
|
53621 | 932 |
|
933 |
subsubsection {* Simple Recursion |
|
934 |
\label{sssec:primrec-simple-recursion} *} |
|
52828 | 935 |
|
52841 | 936 |
text {* |
53621 | 937 |
For simple recursive types, recursive calls on a constructor argument are |
938 |
allowed on the right-hand side: |
|
52841 | 939 |
*} |
940 |
||
53621 | 941 |
(*<*) |
942 |
context dummy_tlist |
|
943 |
begin |
|
944 |
(*>*) |
|
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
945 |
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
|
946 |
"replicate Zero _ = []" | |
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
947 |
"replicate (Suc n) a = a # replicate n a" |
52841 | 948 |
|
53621 | 949 |
text {* \blankline *} |
52843 | 950 |
|
53332 | 951 |
primrec_new at :: "'a list \<Rightarrow> nat \<Rightarrow> 'a" where |
52843 | 952 |
"at (a # as) j = |
953 |
(case j of |
|
53028 | 954 |
Zero \<Rightarrow> a |
52843 | 955 |
| Suc j' \<Rightarrow> at as j')" |
956 |
||
53621 | 957 |
text {* \blankline *} |
958 |
||
52841 | 959 |
primrec_new tfold :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> ('a, 'b) tlist \<Rightarrow> 'b" where |
960 |
"tfold _ (TNil b) = b" | |
|
961 |
"tfold f (TCons a as) = f a (tfold f as)" |
|
53491 | 962 |
(*<*) |
963 |
end |
|
964 |
(*>*) |
|
52841 | 965 |
|
53025 | 966 |
text {* |
53621 | 967 |
\noindent |
968 |
The next example is not primitive recursive, but it can be defined easily using |
|
969 |
@{command fun}. The @{command datatype_new_compat} command is needed to register |
|
970 |
new-style datatypes for use with @{command fun} and @{command function} |
|
971 |
(Section~\ref{sssec:datatype-new-compat}): |
|
53025 | 972 |
*} |
52828 | 973 |
|
53621 | 974 |
datatype_new_compat nat |
975 |
||
976 |
text {* \blankline *} |
|
977 |
||
978 |
fun at_least_two :: "nat \<Rightarrow> bool" where |
|
979 |
"at_least_two (Suc (Suc _)) \<longleftrightarrow> True" | |
|
980 |
"at_least_two _ \<longleftrightarrow> False" |
|
981 |
||
982 |
||
983 |
subsubsection {* Mutual Recursion |
|
984 |
\label{sssec:primrec-mutual-recursion} *} |
|
52828 | 985 |
|
52841 | 986 |
text {* |
53621 | 987 |
The syntax for mutually recursive functions over mutually recursive datatypes |
988 |
is straightforward: |
|
52841 | 989 |
*} |
990 |
||
991 |
primrec_new |
|
53623 | 992 |
nat_of_even_nat :: "even_nat \<Rightarrow> nat" and |
993 |
nat_of_odd_nat :: "odd_nat \<Rightarrow> nat" |
|
52841 | 994 |
where |
53623 | 995 |
"nat_of_even_nat Even_Zero = Zero" | |
996 |
"nat_of_even_nat (Even_Suc n) = Suc (nat_of_odd_nat n)" | |
|
997 |
"nat_of_odd_nat (Odd_Suc n) = Suc (nat_of_even_nat n)" |
|
52841 | 998 |
|
999 |
primrec_new |
|
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1000 |
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
|
1001 |
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
|
1002 |
eval\<^sub>f :: "('a \<Rightarrow> int) \<Rightarrow> ('b \<Rightarrow> int) \<Rightarrow> ('a, 'b) fct \<Rightarrow> int" |
52841 | 1003 |
where |
1004 |
"eval\<^sub>e \<gamma> \<xi> (Term t) = eval\<^sub>t \<gamma> \<xi> t" | |
|
1005 |
"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
|
1006 |
"eval\<^sub>t \<gamma> \<xi> (Factor f) = eval\<^sub>f \<gamma> \<xi> f" | |
52841 | 1007 |
"eval\<^sub>t \<gamma> \<xi> (Prod f t) = eval\<^sub>f \<gamma> \<xi> f + eval\<^sub>t \<gamma> \<xi> t" | |
1008 |
"eval\<^sub>f \<gamma> _ (Const a) = \<gamma> a" | |
|
1009 |
"eval\<^sub>f _ \<xi> (Var b) = \<xi> b" | |
|
1010 |
"eval\<^sub>f \<gamma> \<xi> (Expr e) = eval\<^sub>e \<gamma> \<xi> e" |
|
1011 |
||
53621 | 1012 |
text {* |
1013 |
\noindent |
|
1014 |
Mutual recursion is be possible within a single type, using @{command fun}: |
|
1015 |
*} |
|
52828 | 1016 |
|
53621 | 1017 |
fun |
1018 |
even :: "nat \<Rightarrow> bool" and |
|
1019 |
odd :: "nat \<Rightarrow> bool" |
|
1020 |
where |
|
1021 |
"even Zero = True" | |
|
1022 |
"even (Suc n) = odd n" | |
|
1023 |
"odd Zero = False" | |
|
1024 |
"odd (Suc n) = even n" |
|
1025 |
||
1026 |
||
1027 |
subsubsection {* Nested Recursion |
|
1028 |
\label{sssec:primrec-nested-recursion} *} |
|
1029 |
||
1030 |
text {* |
|
1031 |
In a departure from the old datatype package, nested recursion is normally |
|
1032 |
handled via the map functions of the nesting type constructors. For example, |
|
1033 |
recursive calls are lifted to lists using @{const map}: |
|
1034 |
*} |
|
52828 | 1035 |
|
52843 | 1036 |
(*<*) |
53028 | 1037 |
datatype_new 'a tree\<^sub>f\<^sub>f = Node\<^sub>f\<^sub>f 'a "'a tree\<^sub>f\<^sub>f list" |
53621 | 1038 |
|
1039 |
context dummy_tlist |
|
1040 |
begin |
|
52843 | 1041 |
(*>*) |
53028 | 1042 |
primrec_new at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" where |
1043 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
|
52843 | 1044 |
(case js of |
1045 |
[] \<Rightarrow> a |
|
53028 | 1046 |
| j # js' \<Rightarrow> at (map (\<lambda>t. at\<^sub>f\<^sub>f t js') ts) j)" |
53621 | 1047 |
(*<*) |
1048 |
end |
|
1049 |
(*>*) |
|
52843 | 1050 |
|
53025 | 1051 |
text {* |
53621 | 1052 |
The next example features recursion through the @{text option} type. Although |
53623 | 1053 |
@{text option} is not a new-style datatype, it is registered as a BNF with the |
53621 | 1054 |
map function @{const option_map}: |
53025 | 1055 |
*} |
52843 | 1056 |
|
53335
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1057 |
(*<*) |
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1058 |
locale sum_btree_nested |
53621 | 1059 |
begin |
53335
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1060 |
(*>*) |
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1061 |
primrec_new sum_btree :: "('a\<Colon>{zero,plus}) btree \<Rightarrow> 'a" where |
52843 | 1062 |
"sum_btree (BNode a lt rt) = |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1063 |
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
|
1064 |
the_default 0 (option_map sum_btree rt)" |
53335
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1065 |
(*<*) |
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1066 |
end |
585b2fee55e5
fixed bug in primrec_new (allow indirect recursion through constructor arguments other than the first)
panny
parents:
53332
diff
changeset
|
1067 |
(*>*) |
52843 | 1068 |
|
53136 | 1069 |
text {* |
53621 | 1070 |
\noindent |
1071 |
The same principle applies for arbitrary type constructors through which |
|
1072 |
recursion is possible. Notably, the map function for the function type |
|
1073 |
(@{text \<Rightarrow>}) is simply composition (@{text "op \<circ>"}): |
|
53136 | 1074 |
*} |
52828 | 1075 |
|
53621 | 1076 |
primrec_new ftree_map :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
1077 |
"ftree_map f (FTLeaf x) = FTLeaf (f x)" | |
|
1078 |
"ftree_map f (FTNode g) = FTNode (ftree_map f \<circ> g)" |
|
52828 | 1079 |
|
52843 | 1080 |
text {* |
53621 | 1081 |
\noindent |
1082 |
(No such function is defined by the package because @{typ 'a} is dead in |
|
1083 |
@{typ "'a ftree"}, but we can easily do it ourselves.) |
|
1084 |
*} |
|
1085 |
||
1086 |
||
1087 |
subsubsection {* Nested-as-Mutual Recursion |
|
1088 |
\label{sssec:datatype-nested-as-mutual-recursion} *} |
|
1089 |
||
1090 |
text {* |
|
1091 |
For compatibility with the old package, but also because it is sometimes |
|
1092 |
convenient in its own right, it is possible to treat nested recursive datatypes |
|
1093 |
as mutually recursive ones if the recursion takes place though new-style |
|
1094 |
datatypes. For example: |
|
52843 | 1095 |
*} |
1096 |
||
53331
20440c789759
prove theorem in the right context (that knows about local variables)
traytel
parents:
53330
diff
changeset
|
1097 |
primrec_new |
53028 | 1098 |
at_tree\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" and |
1099 |
at_trees\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f list \<Rightarrow> nat \<Rightarrow> nat list \<Rightarrow> 'a" |
|
52843 | 1100 |
where |
53028 | 1101 |
"at_tree\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
52843 | 1102 |
(case js of |
1103 |
[] \<Rightarrow> a |
|
53028 | 1104 |
| j # js' \<Rightarrow> at_trees\<^sub>f\<^sub>f ts j js')" | |
1105 |
"at_trees\<^sub>f\<^sub>f (t # ts) j = |
|
52843 | 1106 |
(case j of |
53028 | 1107 |
Zero \<Rightarrow> at_tree\<^sub>f\<^sub>f t |
1108 |
| Suc j' \<Rightarrow> at_trees\<^sub>f\<^sub>f ts j')" |
|
52843 | 1109 |
|
53621 | 1110 |
text {* \blankline *} |
1111 |
||
53331
20440c789759
prove theorem in the right context (that knows about local variables)
traytel
parents:
53330
diff
changeset
|
1112 |
primrec_new |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1113 |
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
|
1114 |
sum_btree_option :: "'a btree option \<Rightarrow> 'a" |
52843 | 1115 |
where |
1116 |
"sum_btree (BNode a lt rt) = |
|
53025 | 1117 |
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
|
1118 |
"sum_btree_option None = 0" | |
53025 | 1119 |
"sum_btree_option (Some t) = sum_btree t" |
52843 | 1120 |
|
1121 |
text {* |
|
53621 | 1122 |
|
1123 |
% * can pretend a nested type is mutually recursive (if purely inductive) |
|
1124 |
% * avoids the higher-order map |
|
1125 |
% * e.g. |
|
1126 |
||
53617 | 1127 |
% * this can always be avoided; |
1128 |
% * e.g. in our previous example, we first mapped the recursive |
|
1129 |
% calls, then we used a generic at function to retrieve the result |
|
1130 |
% |
|
1131 |
% * there's no hard-and-fast rule of when to use one or the other, |
|
1132 |
% just like there's no rule when to use fold and when to use |
|
1133 |
% primrec_new |
|
1134 |
% |
|
1135 |
% * higher-order approach, considering nesting as nesting, is more |
|
1136 |
% compositional -- e.g. we saw how we could reuse an existing polymorphic |
|
1137 |
% at or the_default, whereas @{const at_trees\<^sub>f\<^sub>f} is much more specific |
|
1138 |
% |
|
1139 |
% * but: |
|
1140 |
% * is perhaps less intuitive, because it requires higher-order thinking |
|
1141 |
% * may seem inefficient, and indeed with the code generator the |
|
1142 |
% mutually recursive version might be nicer |
|
1143 |
% * is somewhat indirect -- must apply a map first, then compute a result |
|
1144 |
% (cannot mix) |
|
1145 |
% * the auxiliary functions like @{const at_trees\<^sub>f\<^sub>f} are sometimes useful in own right |
|
1146 |
% |
|
1147 |
% * impact on automation unclear |
|
1148 |
% |
|
52843 | 1149 |
*} |
1150 |
||
52824 | 1151 |
|
53617 | 1152 |
subsection {* Command Syntax |
1153 |
\label{ssec:primrec-command-syntax} *} |
|
1154 |
||
1155 |
||
53621 | 1156 |
subsubsection {* \keyw{primrec\_new} |
1157 |
\label{sssec:primrec-new} *} |
|
52828 | 1158 |
|
1159 |
text {* |
|
52840 | 1160 |
Primitive recursive functions have the following general syntax: |
52794 | 1161 |
|
52840 | 1162 |
@{rail " |
53535 | 1163 |
@@{command_def primrec_new} target? fixes \\ @'where' |
52840 | 1164 |
(@{syntax primrec_equation} + '|') |
1165 |
; |
|
53534 | 1166 |
@{syntax_def primrec_equation}: thmdecl? prop |
52840 | 1167 |
"} |
52828 | 1168 |
*} |
1169 |
||
52840 | 1170 |
|
53619 | 1171 |
(* |
52840 | 1172 |
subsection {* Generated Theorems |
1173 |
\label{ssec:primrec-generated-theorems} *} |
|
52824 | 1174 |
|
52828 | 1175 |
text {* |
53617 | 1176 |
% * synthesized nonrecursive definition |
1177 |
% * user specification is rederived from it, exactly as entered |
|
1178 |
% |
|
1179 |
% * induct |
|
1180 |
% * mutualized |
|
1181 |
% * without some needless induction hypotheses if not used |
|
1182 |
% * fold, rec |
|
1183 |
% * mutualized |
|
52828 | 1184 |
*} |
53619 | 1185 |
*) |
1186 |
||
52824 | 1187 |
|
52840 | 1188 |
subsection {* Recursive Default Values for Selectors |
53623 | 1189 |
\label{ssec:primrec-recursive-default-values-for-selectors} *} |
52827 | 1190 |
|
1191 |
text {* |
|
1192 |
A datatype selector @{text un_D} can have a default value for each constructor |
|
1193 |
on which it is not otherwise specified. Occasionally, it is useful to have the |
|
1194 |
default value be defined recursively. This produces a chicken-and-egg situation |
|
53621 | 1195 |
that may seem unsolvable, because the datatype is not introduced yet at the |
52827 | 1196 |
moment when the selectors are introduced. Of course, we can always define the |
1197 |
selectors manually afterward, but we then have to state and prove all the |
|
1198 |
characteristic theorems ourselves instead of letting the package do it. |
|
1199 |
||
1200 |
Fortunately, there is a fairly elegant workaround that relies on overloading and |
|
1201 |
that avoids the tedium of manual derivations: |
|
1202 |
||
1203 |
\begin{enumerate} |
|
1204 |
\setlength{\itemsep}{0pt} |
|
1205 |
||
1206 |
\item |
|
1207 |
Introduce a fully unspecified constant @{text "un_D\<^sub>0 \<Colon> 'a"} using |
|
1208 |
@{keyword consts}. |
|
1209 |
||
1210 |
\item |
|
53535 | 1211 |
Define the datatype, specifying @{text "un_D\<^sub>0"} as the selector's default |
1212 |
value. |
|
52827 | 1213 |
|
1214 |
\item |
|
53535 | 1215 |
Define the behavior of @{text "un_D\<^sub>0"} on values of the newly introduced |
1216 |
datatype using the \keyw{overloading} command. |
|
52827 | 1217 |
|
1218 |
\item |
|
1219 |
Derive the desired equation on @{text un_D} from the characteristic equations |
|
1220 |
for @{text "un_D\<^sub>0"}. |
|
1221 |
\end{enumerate} |
|
1222 |
||
53619 | 1223 |
\noindent |
52827 | 1224 |
The following example illustrates this procedure: |
1225 |
*} |
|
1226 |
||
1227 |
consts termi\<^sub>0 :: 'a |
|
1228 |
||
53619 | 1229 |
text {* \blankline *} |
1230 |
||
53491 | 1231 |
datatype_new ('a, 'b) tlist = |
52827 | 1232 |
TNil (termi: 'b) (defaults ttl: TNil) |
53491 | 1233 |
| TCons (thd: 'a) (ttl : "('a, 'b) tlist") (defaults termi: "\<lambda>_ xs. termi\<^sub>0 xs") |
52827 | 1234 |
|
53619 | 1235 |
text {* \blankline *} |
1236 |
||
52827 | 1237 |
overloading |
53491 | 1238 |
termi\<^sub>0 \<equiv> "termi\<^sub>0 \<Colon> ('a, 'b) tlist \<Rightarrow> 'b" |
52827 | 1239 |
begin |
53491 | 1240 |
primrec_new termi\<^sub>0 :: "('a, 'b) tlist \<Rightarrow> 'b" where |
53621 | 1241 |
"termi\<^sub>0 (TNil y) = y" | |
1242 |
"termi\<^sub>0 (TCons x xs) = termi\<^sub>0 xs" |
|
52827 | 1243 |
end |
1244 |
||
53619 | 1245 |
text {* \blankline *} |
1246 |
||
52827 | 1247 |
lemma terminal_TCons[simp]: "termi (TCons x xs) = termi xs" |
1248 |
by (cases xs) auto |
|
1249 |
||
1250 |
||
53617 | 1251 |
(* |
52828 | 1252 |
subsection {* Compatibility Issues |
53617 | 1253 |
\label{ssec:primrec-compatibility-issues} *} |
52828 | 1254 |
|
1255 |
text {* |
|
53617 | 1256 |
% * different induction in nested case |
1257 |
% * solution: define nested-as-mutual functions with primrec, |
|
1258 |
% and look at .induct |
|
1259 |
% |
|
1260 |
% * different induction and recursor in nested case |
|
1261 |
% * only matters to low-level users; they can define a dummy function to force |
|
1262 |
% generation of mutualized recursor |
|
52828 | 1263 |
*} |
53617 | 1264 |
*) |
52794 | 1265 |
|
1266 |
||
52827 | 1267 |
section {* Defining Codatatypes |
52805 | 1268 |
\label{sec:defining-codatatypes} *} |
1269 |
||
1270 |
text {* |
|
53623 | 1271 |
Codatatypes can be specified using the @{command codatatype} command. The |
1272 |
command is first illustrated through concrete examples featuring different |
|
1273 |
flavors of corecursion. More examples can be found in the directory |
|
1274 |
\verb|~~/src/HOL/BNF/Examples|. The \emph{Archive of Formal Proofs} also |
|
1275 |
includes some useful codatatypes, notably for lazy lists \cite{lochbihler-2010}. |
|
52805 | 1276 |
*} |
52792 | 1277 |
|
52824 | 1278 |
|
53617 | 1279 |
subsection {* Introductory Examples |
1280 |
\label{ssec:codatatype-introductory-examples} *} |
|
52794 | 1281 |
|
53623 | 1282 |
|
1283 |
subsubsection {* Simple Corecursion |
|
1284 |
\label{sssec:codatatype-simple-corecursion} *} |
|
1285 |
||
52805 | 1286 |
text {* |
53623 | 1287 |
Noncorecursive codatatypes coincide with the corresponding datatypes, so |
1288 |
they have no practical uses. \emph{Corecursive codatatypes} have the same syntax |
|
1289 |
as recursive datatypes, except for the command name. For example, here is the |
|
1290 |
definition of lazy lists: |
|
1291 |
*} |
|
1292 |
||
1293 |
codatatype (lset: 'a) llist (map: lmap rel: llist_all2) = |
|
1294 |
lnull: LNil (defaults ltl: LNil) |
|
1295 |
| LCons (lhd: 'a) (ltl: "'a llist") |
|
1296 |
||
1297 |
text {* |
|
1298 |
\noindent |
|
1299 |
Lazy lists can be infinite, such as @{text "LCons 0 (LCons 0 (\<dots>))"} and |
|
1300 |
@{text "LCons 0 (LCons 1 (LCons 2 (\<dots>)))"}. Another interesting type that can |
|
1301 |
be defined as a codatatype is that of the extended natural numbers: |
|
1302 |
*} |
|
1303 |
||
1304 |
codatatype enat = EZero | ESuc nat |
|
1305 |
||
1306 |
text {* |
|
1307 |
\noindent |
|
1308 |
This type has exactly one infinite element, @{text "ESuc (ESuc (ESuc (\<dots>)))"}, |
|
1309 |
that represents $\infty$. In addition, it has finite values of the form |
|
1310 |
@{text "ESuc (\<dots> (ESuc EZero)\<dots>)"}. |
|
52805 | 1311 |
*} |
53623 | 1312 |
|
1313 |
||
1314 |
subsubsection {* Mutual Corecursion |
|
1315 |
\label{sssec:codatatype-mutual-corecursion} *} |
|
1316 |
||
1317 |
text {* |
|
1318 |
\noindent |
|
1319 |
The example below introduces a pair of \emph{mutually corecursive} types: |
|
1320 |
*} |
|
1321 |
||
1322 |
codatatype even_enat = Even_EZero | Even_ESuc odd_enat |
|
1323 |
and odd_enat = Odd_ESuc even_enat |
|
1324 |
||
1325 |
||
1326 |
subsubsection {* Nested Corecursion |
|
1327 |
\label{sssec:codatatype-nested-corecursion} *} |
|
1328 |
||
1329 |
text {* |
|
1330 |
\noindent |
|
1331 |
The next two examples feature \emph{nested corecursion}: |
|
1332 |
*} |
|
1333 |
||
1334 |
codatatype 'a tree\<^sub>i\<^sub>i = Node\<^sub>i\<^sub>i 'a "'a tree\<^sub>i\<^sub>i llist" |
|
1335 |
codatatype 'a tree\<^sub>i\<^sub>s = Node\<^sub>i\<^sub>s 'a "'a tree\<^sub>i\<^sub>s fset" |
|
52805 | 1336 |
|
52824 | 1337 |
|
53617 | 1338 |
subsection {* Command Syntax |
1339 |
\label{ssec:codatatype-command-syntax} *} |
|
52805 | 1340 |
|
53619 | 1341 |
|
53621 | 1342 |
subsubsection {* \keyw{codatatype} |
1343 |
\label{sssec:codatatype} *} |
|
53619 | 1344 |
|
52824 | 1345 |
text {* |
52827 | 1346 |
Definitions of codatatypes have almost exactly the same syntax as for datatypes |
53617 | 1347 |
(Section~\ref{ssec:datatype-command-syntax}), with two exceptions: The command |
53623 | 1348 |
is called @{command codatatype}. The @{text "no_discs_sels"} option is not |
1349 |
available, because destructors are a crucial notion for codatatypes. |
|
1350 |
*} |
|
1351 |
||
1352 |
||
1353 |
subsection {* Generated Constants |
|
1354 |
\label{ssec:codatatype-generated-constants} *} |
|
1355 |
||
1356 |
text {* |
|
1357 |
Given a codatatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
|
1358 |
with $m > 0$ live type variables and $n$ constructors @{text "t.C\<^sub>1"}, |
|
1359 |
\ldots, @{text "t.C\<^sub>n"}, the same auxiliary constants are generated as for |
|
1360 |
datatypes (Section~\ref{ssec:datatype-generated-constants}), except that the |
|
1361 |
iterator and the recursor are replaced by dual concepts: |
|
1362 |
||
1363 |
\begin{itemize} |
|
1364 |
\setlength{\itemsep}{0pt} |
|
1365 |
||
1366 |
\item \relax{Coiterator}: @{text t_unfold} |
|
1367 |
||
1368 |
\item \relax{Corecursor}: @{text t_corec} |
|
1369 |
||
1370 |
\end{itemize} |
|
1371 |
*} |
|
1372 |
||
1373 |
||
1374 |
subsection {* Generated Theorems |
|
1375 |
\label{ssec:codatatype-generated-theorems} *} |
|
1376 |
||
1377 |
text {* |
|
1378 |
The characteristic theorems generated by @{command codatatype} are grouped in |
|
1379 |
three broad categories: |
|
1380 |
||
1381 |
\begin{itemize} |
|
1382 |
\item The \emph{free constructor theorems} are properties about the constructors |
|
1383 |
and destructors that can be derived for any freely generated type. |
|
1384 |
||
1385 |
\item The \emph{functorial theorems} are properties of datatypes related to |
|
1386 |
their BNF nature. |
|
1387 |
||
1388 |
\item The \emph{coinductive theorems} are properties of datatypes related to |
|
1389 |
their coinductive nature. |
|
1390 |
\end{itemize} |
|
1391 |
||
1392 |
\noindent |
|
1393 |
The first two categories are exactly as for datatypes and are described in |
|
53642 | 1394 |
Sections |
1395 |
\ref{sssec:free-constructor-theorems}~and~\ref{sssec:functorial-theorems}. |
|
52824 | 1396 |
*} |
1397 |
||
53617 | 1398 |
|
53623 | 1399 |
subsubsection {* Coinductive Theorems |
1400 |
\label{sssec:coinductive-theorems} *} |
|
1401 |
||
1402 |
text {* |
|
1403 |
The coinductive theorems are as follows: |
|
1404 |
||
1405 |
\begin{indentblock} |
|
1406 |
\begin{description} |
|
1407 |
||
53643 | 1408 |
\item[\begin{tabular}{@ {}l@ {}} |
1409 |
@{text "t."}\hthm{coinduct} @{text "[coinduct t, consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1410 |
\phantom{@{text "t."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1411 |
\end{tabular}] ~ \\ |
|
53623 | 1412 |
@{thm llist.coinduct[no_vars]} |
53617 | 1413 |
|
53643 | 1414 |
\item[\begin{tabular}{@ {}l@ {}} |
1415 |
@{text "t."}\hthm{strong\_coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1416 |
\phantom{@{text "t."}\hthm{strong\_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1417 |
\end{tabular}] ~ \\ |
|
1418 |
@{thm llist.strong_coinduct[no_vars]} |
|
53617 | 1419 |
|
53643 | 1420 |
\item[\begin{tabular}{@ {}l@ {}} |
1421 |
@{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]"} \\ |
|
1422 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{strong\_coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1423 |
\phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{strong\_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1424 |
\end{tabular}] ~ \\ |
|
1425 |
Given $m > 1$ mutually corecursive codatatypes, these coinduction rules can be |
|
1426 |
used to prove $m$ properties simultaneously. |
|
1427 |
||
1428 |
\item[@{text "t."}\hthm{unfold} \rm(@{text "[simp]"})\rm:] ~ \\ |
|
53623 | 1429 |
@{thm llist.unfold(1)[no_vars]} \\ |
1430 |
@{thm llist.unfold(2)[no_vars]} |
|
1431 |
||
53643 | 1432 |
\item[@{text "t."}\hthm{corec} (@{text "[simp]"})\rm:] ~ \\ |
53623 | 1433 |
@{thm llist.corec(1)[no_vars]} \\ |
1434 |
@{thm llist.corec(2)[no_vars]} |
|
1435 |
||
53643 | 1436 |
\item[@{text "t."}\hthm{disc\_unfold} @{text "[simp]"}\rm:] ~ \\ |
1437 |
@{thm llist.disc_unfold(1)[no_vars]} \\ |
|
1438 |
@{thm llist.disc_unfold(2)[no_vars]} |
|
1439 |
||
1440 |
\item[@{text "t."}\hthm{disc\_corec} @{text "[simp]"}\rm:] ~ \\ |
|
1441 |
@{thm llist.disc_corec(1)[no_vars]} \\ |
|
1442 |
@{thm llist.disc_corec(2)[no_vars]} |
|
1443 |
||
1444 |
\item[@{text "t."}\hthm{disc\_unfold\_iff} @{text "[simp]"}\rm:] ~ \\ |
|
1445 |
@{thm llist.disc_unfold_iff(1)[no_vars]} \\ |
|
1446 |
@{thm llist.disc_unfold_iff(2)[no_vars]} |
|
1447 |
||
1448 |
\item[@{text "t."}\hthm{disc\_corec\_iff} @{text "[simp]"}\rm:] ~ \\ |
|
1449 |
@{thm llist.disc_corec_iff(1)[no_vars]} \\ |
|
1450 |
@{thm llist.disc_corec_iff(2)[no_vars]} |
|
1451 |
||
1452 |
\item[@{text "t."}\hthm{sel\_unfold} @{text "[simp]"}\rm:] ~ \\ |
|
1453 |
@{thm llist.sel_unfold(1)[no_vars]} \\ |
|
1454 |
@{thm llist.sel_unfold(2)[no_vars]} |
|
1455 |
||
1456 |
\item[@{text "t."}\hthm{sel\_corec} @{text "[simp]"}\rm:] ~ \\ |
|
1457 |
@{thm llist.sel_corec(1)[no_vars]} \\ |
|
1458 |
@{thm llist.sel_corec(2)[no_vars]} |
|
1459 |
||
53623 | 1460 |
\end{description} |
1461 |
\end{indentblock} |
|
1462 |
||
1463 |
\noindent |
|
1464 |
For convenience, @{command codatatype} also provides the following collection: |
|
1465 |
||
1466 |
\begin{indentblock} |
|
1467 |
\begin{description} |
|
1468 |
||
53643 | 1469 |
\item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.corec}$^*$ @{text t.disc_corec}] ~ \\ |
1470 |
@{text t.disc_corec_iff} @{text t.sel_corec} @{text t.unfold}$^*$ @{text t.disc_unfold} @{text t.disc_unfold_iff} ~ \\ |
|
1471 |
@{text t.sel_unfold} @{text t.map} @{text t.rel_inject} @{text t.rel_distinct} @{text t.sets} |
|
53623 | 1472 |
|
1473 |
\end{description} |
|
1474 |
\end{indentblock} |
|
1475 |
*} |
|
52805 | 1476 |
|
1477 |
||
52827 | 1478 |
section {* Defining Corecursive Functions |
52805 | 1479 |
\label{sec:defining-corecursive-functions} *} |
1480 |
||
1481 |
text {* |
|
53623 | 1482 |
Corecursive functions can be specified using the @{command primcorec} command. |
53643 | 1483 |
Whereas recursive functions consume datatypes one constructor at a time, |
1484 |
corecursive functions construct codatatypes one constructor at a time. |
|
1485 |
||
1486 |
Reflecting a lack of agreement among proponents of coalgebraic methods, Isabelle |
|
1487 |
supports two competing syntaxes for specifying a function $f$: |
|
1488 |
||
1489 |
\begin{itemize} |
|
1490 |
\item Following the \emph{constructor view}, $f$ is specified by equations of |
|
1491 |
the form |
|
1492 |
\[@{text "f x\<^sub>1 \<dots> x\<^sub>n = \<dots>"}\] |
|
1493 |
Corecursive calls on |
|
1494 |
the right-hand side must appear under a guarding codatatype constructor. Haskell |
|
1495 |
and other lazy functional programming languages support this style. |
|
1496 |
||
1497 |
\item Following the \emph{destructor view}, $f$ is specified by implications |
|
1498 |
of the form |
|
1499 |
\[@{text "\<dots> \<Longrightarrow> is_C\<^sub>j (f x\<^sub>1 \<dots> x\<^sub>n)"}\] and |
|
1500 |
equations of the form |
|
1501 |
\[@{text "un_C\<^sub>ji (f x\<^sub>1 \<dots> x\<^sub>n) = \<dots>"}\] where |
|
1502 |
the right-hand side may be a corecursive call or an arbitrary term that does |
|
1503 |
not mention @{text f}. This style is commonly found in the coalgebraic |
|
1504 |
literature. |
|
1505 |
\end{itemize} |
|
1506 |
||
1507 |
\noindent |
|
1508 |
Both styles are available as input syntax to @{command primcorec}. Whichever |
|
1509 |
input syntax is chosen, characteristic theorems following both styles are |
|
1510 |
generated. |
|
52828 | 1511 |
|
1512 |
%%% TODO: partial_function? E.g. for defining tail recursive function on lazy |
|
1513 |
%%% lists (cf. terminal0 in TLList.thy) |
|
52805 | 1514 |
*} |
1515 |
||
52824 | 1516 |
|
53619 | 1517 |
(* |
53617 | 1518 |
subsection {* Introductory Examples |
1519 |
\label{ssec:primcorec-introductory-examples} *} |
|
52805 | 1520 |
|
1521 |
text {* |
|
1522 |
More examples in \verb|~~/src/HOL/BNF/Examples|. |
|
1523 |
*} |
|
53619 | 1524 |
*) |
52805 | 1525 |
|
52824 | 1526 |
|
53617 | 1527 |
subsection {* Command Syntax |
1528 |
\label{ssec:primcorec-command-syntax} *} |
|
1529 |
||
1530 |
||
53621 | 1531 |
subsubsection {* \keyw{primcorec} |
1532 |
\label{sssec:primcorec} *} |
|
52840 | 1533 |
|
1534 |
text {* |
|
53018 | 1535 |
Primitive corecursive definitions have the following general syntax: |
52840 | 1536 |
|
1537 |
@{rail " |
|
53535 | 1538 |
@@{command_def primcorec} target? fixes \\ @'where' |
52840 | 1539 |
(@{syntax primcorec_formula} + '|') |
1540 |
; |
|
53534 | 1541 |
@{syntax_def primcorec_formula}: thmdecl? prop (@'of' (term * ))? |
52840 | 1542 |
"} |
1543 |
*} |
|
52794 | 1544 |
|
52824 | 1545 |
|
53619 | 1546 |
(* |
52840 | 1547 |
subsection {* Generated Theorems |
1548 |
\label{ssec:primcorec-generated-theorems} *} |
|
53619 | 1549 |
*) |
52794 | 1550 |
|
1551 |
||
53623 | 1552 |
(* |
1553 |
subsection {* Recursive Default Values for Selectors |
|
1554 |
\label{ssec:primcorec-recursive-default-values-for-selectors} *} |
|
1555 |
||
1556 |
text {* |
|
1557 |
partial_function to the rescue |
|
1558 |
*} |
|
1559 |
*) |
|
1560 |
||
1561 |
||
52827 | 1562 |
section {* Registering Bounded Natural Functors |
52805 | 1563 |
\label{sec:registering-bounded-natural-functors} *} |
52792 | 1564 |
|
52805 | 1565 |
text {* |
53623 | 1566 |
The (co)datatype package can be set up to allow nested recursion through custom |
1567 |
well-behaved type constructors. The key concept is that of a bounded natural |
|
1568 |
functor (BNF). |
|
52829 | 1569 |
|
52805 | 1570 |
*} |
1571 |
||
52824 | 1572 |
|
53619 | 1573 |
(* |
53617 | 1574 |
subsection {* Introductory Example |
1575 |
\label{ssec:bnf-introductory-example} *} |
|
52805 | 1576 |
|
1577 |
text {* |
|
1578 |
More examples in \verb|~~/src/HOL/BNF/Basic_BNFs.thy| and |
|
1579 |
\verb|~~/src/HOL/BNF/More_BNFs.thy|. |
|
52806 | 1580 |
|
53617 | 1581 |
%Mention distinction between live and dead type arguments; |
1582 |
% * and existence of map, set for those |
|
1583 |
%mention =>. |
|
52805 | 1584 |
*} |
53619 | 1585 |
*) |
52794 | 1586 |
|
52824 | 1587 |
|
53617 | 1588 |
subsection {* Command Syntax |
1589 |
\label{ssec:bnf-command-syntax} *} |
|
1590 |
||
1591 |
||
53621 | 1592 |
subsubsection {* \keyw{bnf} |
1593 |
\label{sssec:bnf} *} |
|
52794 | 1594 |
|
53028 | 1595 |
text {* |
1596 |
@{rail " |
|
53535 | 1597 |
@@{command_def bnf} target? (name ':')? term \\ |
53534 | 1598 |
term_list term term_list term? |
53028 | 1599 |
; |
53534 | 1600 |
X_list: '[' (X + ',') ']' |
53028 | 1601 |
"} |
1602 |
*} |
|
52805 | 1603 |
|
53617 | 1604 |
|
53621 | 1605 |
subsubsection {* \keyw{print\_bnfs} |
1606 |
\label{sssec:print-bnfs} *} |
|
53617 | 1607 |
|
1608 |
text {* |
|
1609 |
@{command print_bnfs} |
|
1610 |
*} |
|
1611 |
||
1612 |
||
1613 |
section {* Deriving Destructors and Theorems for Free Constructors |
|
1614 |
\label{sec:deriving-destructors-and-theorems-for-free-constructors} *} |
|
52794 | 1615 |
|
52805 | 1616 |
text {* |
53623 | 1617 |
The derivation of convenience theorems for types equipped with free constructors, |
1618 |
as performed internally by @{command datatype_new} and @{command codatatype}, |
|
1619 |
is available as a stand-alone command called @{command wrap_free_constructors}. |
|
52794 | 1620 |
|
53617 | 1621 |
% * need for this is rare but may arise if you want e.g. to add destructors to |
1622 |
% a type not introduced by ... |
|
1623 |
% |
|
1624 |
% * also useful for compatibility with old package, e.g. add destructors to |
|
1625 |
% old \keyw{datatype} |
|
1626 |
% |
|
1627 |
% * @{command wrap_free_constructors} |
|
53623 | 1628 |
% * @{text "no_discs_sels"}, @{text "rep_compat"} |
53617 | 1629 |
% * hack to have both co and nonco view via locale (cf. ext nats) |
52805 | 1630 |
*} |
52792 | 1631 |
|
52824 | 1632 |
|
53619 | 1633 |
(* |
53617 | 1634 |
subsection {* Introductory Example |
1635 |
\label{ssec:ctors-introductory-example} *} |
|
53619 | 1636 |
*) |
52794 | 1637 |
|
52824 | 1638 |
|
53617 | 1639 |
subsection {* Command Syntax |
1640 |
\label{ssec:ctors-command-syntax} *} |
|
1641 |
||
1642 |
||
53621 | 1643 |
subsubsection {* \keyw{wrap\_free\_constructors} |
1644 |
\label{sssec:wrap-free-constructors} *} |
|
52828 | 1645 |
|
53018 | 1646 |
text {* |
1647 |
Free constructor wrapping has the following general syntax: |
|
1648 |
||
1649 |
@{rail " |
|
53535 | 1650 |
@@{command_def wrap_free_constructors} target? @{syntax dt_options} \\ |
53534 | 1651 |
term_list name @{syntax fc_discs_sels}? |
53018 | 1652 |
; |
53534 | 1653 |
@{syntax_def fc_discs_sels}: name_list (name_list_list name_term_list_list? )? |
53018 | 1654 |
; |
53534 | 1655 |
@{syntax_def name_term}: (name ':' term) |
53018 | 1656 |
"} |
1657 |
||
53617 | 1658 |
% options: no_discs_sels rep_compat |
53028 | 1659 |
|
53617 | 1660 |
% X_list is as for BNF |
53028 | 1661 |
|
53542 | 1662 |
Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems. |
53018 | 1663 |
*} |
52828 | 1664 |
|
52794 | 1665 |
|
53617 | 1666 |
(* |
52827 | 1667 |
section {* Standard ML Interface |
52805 | 1668 |
\label{sec:standard-ml-interface} *} |
52792 | 1669 |
|
52805 | 1670 |
text {* |
53623 | 1671 |
The package's programmatic interface. |
52805 | 1672 |
*} |
53617 | 1673 |
*) |
52794 | 1674 |
|
1675 |
||
53617 | 1676 |
(* |
52827 | 1677 |
section {* Interoperability |
52805 | 1678 |
\label{sec:interoperability} *} |
52794 | 1679 |
|
52805 | 1680 |
text {* |
53623 | 1681 |
The package's interaction with other Isabelle packages and tools, such as the |
1682 |
code generator and the counterexample generators. |
|
52805 | 1683 |
*} |
52794 | 1684 |
|
52824 | 1685 |
|
52828 | 1686 |
subsection {* Transfer and Lifting |
1687 |
\label{ssec:transfer-and-lifting} *} |
|
52794 | 1688 |
|
52824 | 1689 |
|
52828 | 1690 |
subsection {* Code Generator |
1691 |
\label{ssec:code-generator} *} |
|
52794 | 1692 |
|
52824 | 1693 |
|
52828 | 1694 |
subsection {* Quickcheck |
1695 |
\label{ssec:quickcheck} *} |
|
52794 | 1696 |
|
52824 | 1697 |
|
52828 | 1698 |
subsection {* Nitpick |
1699 |
\label{ssec:nitpick} *} |
|
52794 | 1700 |
|
52824 | 1701 |
|
52828 | 1702 |
subsection {* Nominal Isabelle |
1703 |
\label{ssec:nominal-isabelle} *} |
|
53617 | 1704 |
*) |
52794 | 1705 |
|
52805 | 1706 |
|
53617 | 1707 |
(* |
52827 | 1708 |
section {* Known Bugs and Limitations |
52805 | 1709 |
\label{sec:known-bugs-and-limitations} *} |
1710 |
||
1711 |
text {* |
|
53623 | 1712 |
Known open issues of the package. |
52805 | 1713 |
*} |
52794 | 1714 |
|
1715 |
text {* |
|
53617 | 1716 |
%* primcorec is unfinished |
1717 |
% |
|
1718 |
%* slow n-ary mutual (co)datatype, avoid as much as possible (e.g. using nesting) |
|
1719 |
% |
|
1720 |
%* issues with HOL-Proofs? |
|
1721 |
% |
|
1722 |
%* partial documentation |
|
1723 |
% |
|
1724 |
%* no way to register "sum" and "prod" as (co)datatypes to enable N2M reduction for them |
|
1725 |
% (for @{command datatype_new_compat} and prim(co)rec) |
|
1726 |
% |
|
53619 | 1727 |
% * a fortiori, no way to register same type as both data- and codatatype |
53617 | 1728 |
% |
1729 |
%* no recursion through unused arguments (unlike with the old package) |
|
1730 |
% |
|
1731 |
%* in a locale, cannot use locally fixed types (because of limitation in typedef)? |
|
53619 | 1732 |
% |
1733 |
% *names of variables suboptimal |
|
52822 | 1734 |
*} |
1735 |
||
1736 |
||
52827 | 1737 |
section {* Acknowledgments |
52822 | 1738 |
\label{sec:acknowledgments} *} |
1739 |
||
1740 |
text {* |
|
53617 | 1741 |
Tobias Nipkow and Makarius Wenzel have encouraged us to implement the new |
1742 |
(co)datatype package. Andreas Lochbihler provided lots of comments on earlier |
|
1743 |
versions of the package, especially for the coinductive part. Brian Huffman |
|
1744 |
suggested major simplifications to the internal constructions, much of which has |
|
1745 |
yet to be implemented. Florian Haftmann and Christian Urban provided general |
|
1746 |
advice advice on Isabelle and package writing. Stefan Milius and Lutz Schr\"oder |
|
1747 |
suggested an elegant proof to eliminate one of the BNF assumptions. |
|
52794 | 1748 |
*} |
53617 | 1749 |
*) |
1750 |
||
52792 | 1751 |
|
1752 |
end |