author | desharna |
Thu, 03 Jul 2014 11:30:23 +0200 | |
changeset 57494 | c29729f764b1 |
parent 57490 | afc7081f19d4 |
child 57526 | 7027cf5c1f2c |
permissions | -rw-r--r-- |
52792 | 1 |
(* Title: Doc/Datatypes/Datatypes.thy |
2 |
Author: Jasmin Blanchette, TU Muenchen |
|
57079 | 3 |
Author: Martin Desharnais, Ecole de technologie superieure |
53617 | 4 |
Author: Lorenz Panny, TU Muenchen |
5 |
Author: Andrei Popescu, TU Muenchen |
|
6 |
Author: Dmitriy Traytel, TU Muenchen |
|
52792 | 7 |
|
8 |
Tutorial for (co)datatype definitions with the new package. |
|
9 |
*) |
|
10 |
||
11 |
theory Datatypes |
|
55073 | 12 |
imports |
13 |
Setup |
|
56942 | 14 |
"~~/src/HOL/Library/BNF_Axiomatization" |
55350 | 15 |
"~~/src/HOL/Library/Cardinal_Notations" |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
16 |
"~~/src/HOL/Library/FSet" |
55073 | 17 |
"~~/src/HOL/Library/Simps_Case_Conv" |
52792 | 18 |
begin |
19 |
||
52828 | 20 |
section {* Introduction |
21 |
\label{sec:introduction} *} |
|
52792 | 22 |
|
23 |
text {* |
|
53028 | 24 |
The 2013 edition of Isabelle introduced a new definitional package for freely |
25 |
generated datatypes and codatatypes. The datatype support is similar to that |
|
26 |
provided by the earlier package due to Berghofer and Wenzel |
|
27 |
\cite{Berghofer-Wenzel:1999:TPHOL}, documented in the Isar reference manual |
|
53535 | 28 |
\cite{isabelle-isar-ref}; indeed, replacing the keyword \keyw{datatype} by |
53028 | 29 |
@{command datatype_new} is usually all that is needed to port existing theories |
30 |
to use the new package. |
|
52840 | 31 |
|
52841 | 32 |
Perhaps the main advantage of the new package is that it supports recursion |
53619 | 33 |
through a large class of non-datatypes, such as finite sets: |
52792 | 34 |
*} |
35 |
||
53644 | 36 |
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 | 37 |
|
38 |
text {* |
|
52794 | 39 |
\noindent |
53025 | 40 |
Another strong point is the support for local definitions: |
52792 | 41 |
*} |
42 |
||
52805 | 43 |
context linorder |
44 |
begin |
|
52841 | 45 |
datatype_new flag = Less | Eq | Greater |
52805 | 46 |
end |
52792 | 47 |
|
48 |
text {* |
|
52794 | 49 |
\noindent |
54187 | 50 |
Furthermore, the package provides a lot of convenience, including automatically |
51 |
generated discriminators, selectors, and relators as well as a wealth of |
|
52 |
properties about them. |
|
53 |
||
54 |
In addition to inductive datatypes, the new package supports coinductive |
|
55 |
datatypes, or \emph{codatatypes}, which allow infinite values. For example, the |
|
56 |
following command introduces the type of lazy lists, which comprises both finite |
|
57 |
and infinite values: |
|
52794 | 58 |
*} |
59 |
||
53623 | 60 |
(*<*) |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
61 |
locale early |
54072 | 62 |
locale late |
53623 | 63 |
(*>*) |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
64 |
codatatype (*<*)(in early) (*>*)'a llist = LNil | LCons 'a "'a llist" |
52794 | 65 |
|
66 |
text {* |
|
67 |
\noindent |
|
52840 | 68 |
Mixed inductive--coinductive recursion is possible via nesting. Compare the |
53028 | 69 |
following four Rose tree examples: |
52794 | 70 |
*} |
71 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
72 |
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
|
73 |
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
|
74 |
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
|
75 |
codatatype (*<*)(in early) (*>*)'a tree\<^sub>i\<^sub>i = Node\<^sub>i\<^sub>i 'a "'a tree\<^sub>i\<^sub>i llist" |
52792 | 76 |
|
52794 | 77 |
text {* |
54187 | 78 |
The first two tree types allow only paths of finite length, whereas the last two |
79 |
allow infinite paths. Orthogonally, the nodes in the first and third types have |
|
80 |
finitely many direct subtrees, whereas those of the second and fourth may have |
|
81 |
infinite branching. |
|
52840 | 82 |
|
55073 | 83 |
The package is part of @{theory Main}. Additional functionality is provided by |
56942 | 84 |
the theory @{theory BNF_Axiomatization}, located in the directory |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
85 |
\verb|~~/src/HOL/Library|. |
55073 | 86 |
|
52805 | 87 |
The package, like its predecessor, fully adheres to the LCF philosophy |
88 |
\cite{mgordon79}: The characteristic theorems associated with the specified |
|
89 |
(co)datatypes are derived rather than introduced axiomatically.% |
|
53543 | 90 |
\footnote{If the @{text quick_and_dirty} option is enabled, some of the |
52841 | 91 |
internal constructions and most of the internal proof obligations are skipped.} |
52805 | 92 |
The package's metatheory is described in a pair of papers |
53552 | 93 |
\cite{traytel-et-al-2012,blanchette-et-al-wit}. The central notion is that of a |
94 |
\emph{bounded natural functor} (BNF)---a well-behaved type constructor for which |
|
95 |
nested (co)recursion is supported. |
|
52792 | 96 |
|
52794 | 97 |
This tutorial is organized as follows: |
98 |
||
52805 | 99 |
\begin{itemize} |
52822 | 100 |
\setlength{\itemsep}{0pt} |
101 |
||
52805 | 102 |
\item Section \ref{sec:defining-datatypes}, ``Defining Datatypes,'' |
52822 | 103 |
describes how to specify datatypes using the @{command datatype_new} command. |
52805 | 104 |
|
53018 | 105 |
\item Section \ref{sec:defining-recursive-functions}, ``Defining Recursive |
52805 | 106 |
Functions,'' describes how to specify recursive functions using |
56655 | 107 |
@{command primrec}. |
52805 | 108 |
|
109 |
\item Section \ref{sec:defining-codatatypes}, ``Defining Codatatypes,'' |
|
53829 | 110 |
describes how to specify codatatypes using the @{command codatatype} command. |
52805 | 111 |
|
53018 | 112 |
\item Section \ref{sec:defining-corecursive-functions}, ``Defining Corecursive |
52805 | 113 |
Functions,'' describes how to specify corecursive functions using the |
53826 | 114 |
@{command primcorec} and @{command primcorecursive} commands. |
52794 | 115 |
|
55351 | 116 |
\item Section \ref{sec:introducing-bounded-natural-functors}, ``Introducing |
53552 | 117 |
Bounded Natural Functors,'' explains how to use the @{command bnf} command |
118 |
to register arbitrary type constructors as BNFs. |
|
52805 | 119 |
|
53552 | 120 |
\item Section |
53617 | 121 |
\ref{sec:deriving-destructors-and-theorems-for-free-constructors}, |
122 |
``Deriving Destructors and Theorems for Free Constructors,'' explains how to |
|
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
123 |
use the command @{command free_constructors} to derive destructor constants |
53552 | 124 |
and theorems for freely generated types, as performed internally by @{command |
53829 | 125 |
datatype_new} and @{command codatatype}. |
52794 | 126 |
|
53617 | 127 |
%\item Section \ref{sec:standard-ml-interface}, ``Standard ML Interface,'' |
128 |
%describes the package's programmatic interface. |
|
52794 | 129 |
|
53617 | 130 |
%\item Section \ref{sec:interoperability}, ``Interoperability,'' |
131 |
%is concerned with the packages' interaction with other Isabelle packages and |
|
132 |
%tools, such as the code generator and the counterexample generators. |
|
52805 | 133 |
|
53617 | 134 |
%\item Section \ref{sec:known-bugs-and-limitations}, ``Known Bugs and |
135 |
%Limitations,'' concludes with known open issues at the time of writing. |
|
52805 | 136 |
\end{itemize} |
52822 | 137 |
|
138 |
||
139 |
\newbox\boxA |
|
54185 | 140 |
\setbox\boxA=\hbox{\texttt{NOSPAM}} |
141 |
||
142 |
\newcommand\authoremaili{\texttt{blan{\color{white}NOSPAM}\kern-\wd\boxA{}chette@\allowbreak |
|
52822 | 143 |
in.\allowbreak tum.\allowbreak de}} |
57079 | 144 |
\newcommand\authoremailii{\texttt{desh{\color{white}NOSPAM}\kern-\wd\boxA{}arna@\allowbreak |
145 |
in.\allowbreak tum.\allowbreak de}} |
|
146 |
\newcommand\authoremailiii{\texttt{lore{\color{white}NOSPAM}\kern-\wd\boxA{}nz.panny@\allowbreak |
|
52822 | 147 |
in.\allowbreak tum.\allowbreak de}} |
57079 | 148 |
\newcommand\authoremailiv{\texttt{pope{\color{white}NOSPAM}\kern-\wd\boxA{}scua@\allowbreak |
149 |
in.\allowbreak tum.\allowbreak de}} |
|
150 |
\newcommand\authoremailv{\texttt{tray{\color{white}NOSPAM}\kern-\wd\boxA{}tel@\allowbreak |
|
52822 | 151 |
in.\allowbreak tum.\allowbreak de}} |
152 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
153 |
The command @{command datatype_new} is expected to replace \keyw{datatype} in a |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
154 |
future release. Authors of new theories are encouraged to use the new commands, |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
155 |
and maintainers of older theories may want to consider upgrading. |
52841 | 156 |
|
157 |
Comments and bug reports concerning either the tool or this tutorial should be |
|
53028 | 158 |
directed to the authors at \authoremaili, \authoremailii, \authoremailiii, |
57079 | 159 |
\authoremailiv, and \authoremailv. |
52794 | 160 |
*} |
161 |
||
53491 | 162 |
|
52827 | 163 |
section {* Defining Datatypes |
52805 | 164 |
\label{sec:defining-datatypes} *} |
165 |
||
166 |
text {* |
|
53646 | 167 |
Datatypes can be specified using the @{command datatype_new} command. |
52805 | 168 |
*} |
52792 | 169 |
|
52824 | 170 |
|
53617 | 171 |
subsection {* Introductory Examples |
172 |
\label{ssec:datatype-introductory-examples} *} |
|
52794 | 173 |
|
53646 | 174 |
text {* |
175 |
Datatypes are illustrated through concrete examples featuring different flavors |
|
176 |
of recursion. More examples can be found in the directory |
|
54185 | 177 |
\verb|~~/src/HOL/|\allowbreak\verb|BNF/Examples|. |
53646 | 178 |
*} |
53621 | 179 |
|
180 |
subsubsection {* Nonrecursive Types |
|
181 |
\label{sssec:datatype-nonrecursive-types} *} |
|
52794 | 182 |
|
52805 | 183 |
text {* |
53028 | 184 |
Datatypes are introduced by specifying the desired names and argument types for |
53491 | 185 |
their constructors. \emph{Enumeration} types are the simplest form of datatype. |
53028 | 186 |
All their constructors are nullary: |
52805 | 187 |
*} |
188 |
||
52828 | 189 |
datatype_new trool = Truue | Faalse | Perhaaps |
52805 | 190 |
|
191 |
text {* |
|
53028 | 192 |
\noindent |
53491 | 193 |
Here, @{const Truue}, @{const Faalse}, and @{const Perhaaps} have the type @{typ trool}. |
53028 | 194 |
|
195 |
Polymorphic types are possible, such as the following option type, modeled after |
|
196 |
its homologue from the @{theory Option} theory: |
|
52805 | 197 |
*} |
198 |
||
53025 | 199 |
(*<*) |
56995 | 200 |
hide_const None Some map_option |
54958
4933165fd112
do not use wrong constructor in auto-generated proof goal
panny
parents:
54955
diff
changeset
|
201 |
hide_type option |
53025 | 202 |
(*>*) |
203 |
datatype_new 'a option = None | Some 'a |
|
52805 | 204 |
|
205 |
text {* |
|
53028 | 206 |
\noindent |
53491 | 207 |
The constructors are @{text "None :: 'a option"} and |
208 |
@{text "Some :: 'a \<Rightarrow> 'a option"}. |
|
53028 | 209 |
|
210 |
The next example has three type parameters: |
|
52805 | 211 |
*} |
212 |
||
213 |
datatype_new ('a, 'b, 'c) triple = Triple 'a 'b 'c |
|
214 |
||
53028 | 215 |
text {* |
216 |
\noindent |
|
217 |
The constructor is |
|
53491 | 218 |
@{text "Triple :: 'a \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> ('a, 'b, 'c) triple"}. |
53028 | 219 |
Unlike in Standard ML, curried constructors are supported. The uncurried variant |
220 |
is also possible: |
|
221 |
*} |
|
222 |
||
223 |
datatype_new ('a, 'b, 'c) triple\<^sub>u = Triple\<^sub>u "'a * 'b * 'c" |
|
224 |
||
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
225 |
text {* |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
226 |
\noindent |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
227 |
Occurrences of nonatomic types on the right-hand side of the equal sign must be |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
228 |
enclosed in double quotes, as is customary in Isabelle. |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
229 |
*} |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
230 |
|
52824 | 231 |
|
53621 | 232 |
subsubsection {* Simple Recursion |
233 |
\label{sssec:datatype-simple-recursion} *} |
|
52794 | 234 |
|
52805 | 235 |
text {* |
53491 | 236 |
Natural numbers are the simplest example of a recursive type: |
52805 | 237 |
*} |
238 |
||
53332 | 239 |
datatype_new nat = Zero | Suc nat |
52805 | 240 |
|
241 |
text {* |
|
53491 | 242 |
\noindent |
54187 | 243 |
Lists were shown in the introduction. Terminated lists are a variant that |
244 |
stores a value of type @{typ 'b} at the very end: |
|
52805 | 245 |
*} |
246 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
247 |
datatype_new (*<*)(in early) (*>*)('a, 'b) tlist = TNil 'b | TCons 'a "('a, 'b) tlist" |
52805 | 248 |
|
52824 | 249 |
|
53621 | 250 |
subsubsection {* Mutual Recursion |
251 |
\label{sssec:datatype-mutual-recursion} *} |
|
52794 | 252 |
|
52805 | 253 |
text {* |
53552 | 254 |
\emph{Mutually recursive} types are introduced simultaneously and may refer to |
255 |
each other. The example below introduces a pair of types for even and odd |
|
256 |
natural numbers: |
|
52805 | 257 |
*} |
258 |
||
53623 | 259 |
datatype_new even_nat = Even_Zero | Even_Suc odd_nat |
260 |
and odd_nat = Odd_Suc even_nat |
|
52805 | 261 |
|
262 |
text {* |
|
53491 | 263 |
\noindent |
264 |
Arithmetic expressions are defined via terms, terms via factors, and factors via |
|
265 |
expressions: |
|
52805 | 266 |
*} |
267 |
||
52841 | 268 |
datatype_new ('a, 'b) exp = |
269 |
Term "('a, 'b) trm" | Sum "('a, 'b) trm" "('a, 'b) exp" |
|
52805 | 270 |
and ('a, 'b) trm = |
52841 | 271 |
Factor "('a, 'b) fct" | Prod "('a, 'b) fct" "('a, 'b) trm" |
272 |
and ('a, 'b) fct = |
|
273 |
Const 'a | Var 'b | Expr "('a, 'b) exp" |
|
52805 | 274 |
|
52824 | 275 |
|
53621 | 276 |
subsubsection {* Nested Recursion |
277 |
\label{sssec:datatype-nested-recursion} *} |
|
52794 | 278 |
|
52805 | 279 |
text {* |
53491 | 280 |
\emph{Nested recursion} occurs when recursive occurrences of a type appear under |
281 |
a type constructor. The introduction showed some examples of trees with nesting |
|
53675 | 282 |
through lists. A more complex example, that reuses our @{type option} type, |
53491 | 283 |
follows: |
52805 | 284 |
*} |
285 |
||
52843 | 286 |
datatype_new 'a btree = |
53025 | 287 |
BNode 'a "'a btree option" "'a btree option" |
52805 | 288 |
|
289 |
text {* |
|
53491 | 290 |
\noindent |
291 |
Not all nestings are admissible. For example, this command will fail: |
|
52805 | 292 |
*} |
293 |
||
54187 | 294 |
datatype_new 'a wrong = W1 | W2 (*<*)'a |
53542 | 295 |
typ (*>*)"'a wrong \<Rightarrow> 'a" |
52806 | 296 |
|
297 |
text {* |
|
53491 | 298 |
\noindent |
299 |
The issue is that the function arrow @{text "\<Rightarrow>"} allows recursion |
|
300 |
only through its right-hand side. This issue is inherited by polymorphic |
|
301 |
datatypes defined in terms of~@{text "\<Rightarrow>"}: |
|
302 |
*} |
|
303 |
||
55350 | 304 |
datatype_new ('a, 'b) fun_copy = Fun "'a \<Rightarrow> 'b" |
54187 | 305 |
datatype_new 'a also_wrong = W1 | W2 (*<*)'a |
55350 | 306 |
typ (*>*)"('a also_wrong, 'a) fun_copy" |
53491 | 307 |
|
308 |
text {* |
|
309 |
\noindent |
|
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
310 |
The following definition of @{typ 'a}-branching trees is legal: |
53621 | 311 |
*} |
312 |
||
313 |
datatype_new 'a ftree = FTLeaf 'a | FTNode "'a \<Rightarrow> 'a ftree" |
|
314 |
||
315 |
text {* |
|
316 |
\noindent |
|
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
317 |
And so is the definition of hereditarily finite sets: |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
318 |
*} |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
319 |
|
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
320 |
datatype_new hfset = HFSet "hfset fset" |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
321 |
|
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
322 |
text {* |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
323 |
\noindent |
53491 | 324 |
In general, type constructors @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
325 |
allow recursion on a subset of their type arguments @{text 'a\<^sub>1}, \ldots, |
|
326 |
@{text 'a\<^sub>m}. These type arguments are called \emph{live}; the remaining |
|
327 |
type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and |
|
55350 | 328 |
@{typ "('a, 'b) fun_copy"}, the type variable @{typ 'a} is dead and |
329 |
@{typ 'b} is live. |
|
53552 | 330 |
|
53647 | 331 |
Type constructors must be registered as BNFs to have live arguments. This is |
332 |
done automatically for datatypes and codatatypes introduced by the @{command |
|
53829 | 333 |
datatype_new} and @{command codatatype} commands. |
55351 | 334 |
Section~\ref{sec:introducing-bounded-natural-functors} explains how to |
335 |
register arbitrary type constructors as BNFs. |
|
54187 | 336 |
|
337 |
Here is another example that fails: |
|
52806 | 338 |
*} |
339 |
||
54187 | 340 |
datatype_new 'a pow_list = PNil 'a (*<*)'a |
341 |
datatype_new 'a pow_list' = PNil' 'a (*>*)| PCons "('a * 'a) pow_list" |
|
342 |
||
343 |
text {* |
|
344 |
\noindent |
|
55351 | 345 |
This attempted definition features a different flavor of nesting, where the |
346 |
recursive call in the type specification occurs around (rather than inside) |
|
347 |
another type constructor. |
|
54187 | 348 |
*} |
349 |
||
350 |
subsubsection {* Auxiliary Constants and Properties |
|
351 |
\label{sssec:datatype-auxiliary-constants-and-properties} *} |
|
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 |
|
54187 | 357 |
custom names. In the example below, the familiar names @{text null}, @{text hd}, |
358 |
@{text tl}, @{text set}, @{text map}, and @{text list_all2}, override the |
|
359 |
default names @{text is_Nil}, @{text un_Cons1}, @{text un_Cons2}, |
|
54491 | 360 |
@{text set_list}, @{text map_list}, and @{text rel_list}: |
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 |
56995 | 373 |
hide_const Nil Cons hd tl set map list_all2 rec_list size_list |
53025 | 374 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
375 |
context early begin |
52841 | 376 |
(*>*) |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
377 |
datatype_new (set: 'a) list = |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
378 |
null: Nil |
53025 | 379 |
| Cons (hd: 'a) (tl: "'a list") |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
380 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
381 |
map: map |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
382 |
rel: list_all2 |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
383 |
where |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
384 |
"tl Nil = Nil" |
52822 | 385 |
|
386 |
text {* |
|
387 |
\noindent |
|
55353 | 388 |
The types of the constants that appear in the specification are listed below. |
55351 | 389 |
|
390 |
\medskip |
|
54187 | 391 |
|
392 |
\begin{tabular}{@ {}ll@ {}} |
|
393 |
Constructors: & |
|
394 |
@{text "Nil \<Colon> 'a list"} \\ |
|
395 |
& |
|
396 |
@{text "Cons \<Colon> 'a \<Rightarrow> 'a list \<Rightarrow> 'a list"} \\ |
|
397 |
Discriminator: & |
|
398 |
@{text "null \<Colon> 'a list \<Rightarrow> bool"} \\ |
|
399 |
Selectors: & |
|
400 |
@{text "hd \<Colon> 'a list \<Rightarrow> 'a"} \\ |
|
401 |
& |
|
402 |
@{text "tl \<Colon> 'a list \<Rightarrow> 'a list"} \\ |
|
403 |
Set function: & |
|
404 |
@{text "set \<Colon> 'a list \<Rightarrow> 'a set"} \\ |
|
405 |
Map function: & |
|
406 |
@{text "map \<Colon> ('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list"} \\ |
|
407 |
Relator: & |
|
408 |
@{text "list_all2 \<Colon> ('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> 'a list \<Rightarrow> 'b list \<Rightarrow> bool"} |
|
409 |
\end{tabular} |
|
410 |
||
55351 | 411 |
\medskip |
412 |
||
54187 | 413 |
The discriminator @{const null} and the selectors @{const hd} and @{const tl} |
55351 | 414 |
are characterized by the following conditional equations: |
52822 | 415 |
% |
53025 | 416 |
\[@{thm list.collapse(1)[of xs, no_vars]} |
417 |
\qquad @{thm list.collapse(2)[of xs, no_vars]}\] |
|
52822 | 418 |
% |
54187 | 419 |
For two-constructor datatypes, a single discriminator constant is sufficient. |
420 |
The discriminator associated with @{const Cons} is simply |
|
53491 | 421 |
@{term "\<lambda>xs. \<not> null xs"}. |
52822 | 422 |
|
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
423 |
The \keyw{where} clause at the end of the command specifies a default value for |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
424 |
selectors applied to constructors on which they are not a priori specified. |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
425 |
Here, it is used to ensure that the tail of the empty list is itself (instead of |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
426 |
being left unspecified). |
52822 | 427 |
|
53617 | 428 |
Because @{const Nil} is nullary, it is also possible to use |
57091 | 429 |
@{term "\<lambda>xs. xs = Nil"} as a discriminator. This is the default behavior |
430 |
if we omit the identifier @{const null} and the associated colon. Some users |
|
431 |
argue against this, because the mixture of constructors and selectors in the |
|
432 |
characteristic theorems can lead Isabelle's automation to switch between the |
|
433 |
constructor and the destructor view in surprising ways. |
|
52822 | 434 |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
435 |
The usual mixfix syntax annotations are available for both types and |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
436 |
constructors. For example: |
52805 | 437 |
*} |
52794 | 438 |
|
53025 | 439 |
(*<*) |
440 |
end |
|
441 |
(*>*) |
|
53552 | 442 |
datatype_new ('a, 'b) prod (infixr "*" 20) = Pair 'a 'b |
443 |
||
444 |
text {* \blankline *} |
|
52822 | 445 |
|
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
446 |
datatype_new (set: 'a) list = |
52822 | 447 |
null: Nil ("[]") |
52841 | 448 |
| Cons (hd: 'a) (tl: "'a list") (infixr "#" 65) |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
449 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
450 |
map: map |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
451 |
rel: list_all2 |
52841 | 452 |
|
453 |
text {* |
|
53535 | 454 |
\noindent |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
455 |
Incidentally, this is how the traditional syntax can be set up: |
52841 | 456 |
*} |
457 |
||
458 |
syntax "_list" :: "args \<Rightarrow> 'a list" ("[(_)]") |
|
459 |
||
53552 | 460 |
text {* \blankline *} |
461 |
||
52841 | 462 |
translations |
463 |
"[x, xs]" == "x # [xs]" |
|
464 |
"[x]" == "x # []" |
|
52822 | 465 |
|
52824 | 466 |
|
53617 | 467 |
subsection {* Command Syntax |
468 |
\label{ssec:datatype-command-syntax} *} |
|
469 |
||
470 |
||
53621 | 471 |
subsubsection {* \keyw{datatype\_new} |
472 |
\label{sssec:datatype-new} *} |
|
52794 | 473 |
|
52822 | 474 |
text {* |
53829 | 475 |
\begin{matharray}{rcl} |
476 |
@{command_def "datatype_new"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
477 |
\end{matharray} |
|
52822 | 478 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
479 |
@{rail \<open> |
55029
61a6bf7d4b02
clarified @{rail} syntax: prefer explicit \<newline> symbol;
wenzelm
parents:
54958
diff
changeset
|
480 |
@@{command datatype_new} target? @{syntax dt_options}? \<newline> |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
481 |
(@{syntax dt_name} '=' (@{syntax dt_ctor} + '|') \<newline> |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
482 |
@{syntax map_rel}? (@'where' (prop + '|'))? + @'and') |
52828 | 483 |
; |
57094
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
484 |
@{syntax_def dt_options}: '(' (('discs_sels' | 'no_code') + ',') ')' |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
485 |
; |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
486 |
@{syntax_def map_rel}: @'for' ((('map' | 'rel') ':' name) +) |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
487 |
\<close>} |
52824 | 488 |
|
55351 | 489 |
\medskip |
490 |
||
491 |
\noindent |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
492 |
The @{command datatype_new} command introduces a set of mutually recursive |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
493 |
datatypes specified by their constructors. |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
494 |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
495 |
The syntactic entity \synt{target} can be used to specify a local |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
496 |
context (e.g., @{text "(in linorder)"} \cite{isabelle-isar-ref}), |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
497 |
and \synt{prop} denotes a HOL proposition. |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
498 |
|
56124 | 499 |
The optional target is optionally followed by one or both of the following |
500 |
options: |
|
52822 | 501 |
|
52824 | 502 |
\begin{itemize} |
503 |
\setlength{\itemsep}{0pt} |
|
504 |
||
505 |
\item |
|
57094
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
506 |
The @{text "discs_sels"} option indicates that discriminators and selectors |
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
507 |
should be generated. The option is implicitly enabled if names are specified for |
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
508 |
discriminators or selectors. |
52822 | 509 |
|
52824 | 510 |
\item |
54626 | 511 |
The @{text "no_code"} option indicates that the datatype should not be |
512 |
registered for code generation. |
|
52824 | 513 |
\end{itemize} |
52822 | 514 |
|
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
515 |
The optional \keyw{where} clause specifies default values for selectors. |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
516 |
Each proposition must be an equation of the form |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
517 |
@{text "un_D (C \<dots>) = \<dots>"}, where @{text C} is a constructor and |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
518 |
@{text un_D} is a selector. |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
519 |
|
52827 | 520 |
The left-hand sides of the datatype equations specify the name of the type to |
53534 | 521 |
define, its type parameters, and additional information: |
52822 | 522 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
523 |
@{rail \<open> |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
524 |
@{syntax_def dt_name}: @{syntax tyargs}? name mixfix? |
52824 | 525 |
; |
57092 | 526 |
@{syntax_def tyargs}: typefree | '(' (('dead' | name ':')? typefree + ',') ')' |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
527 |
\<close>} |
52822 | 528 |
|
55351 | 529 |
\medskip |
530 |
||
52827 | 531 |
\noindent |
55474 | 532 |
The syntactic entity \synt{name} denotes an identifier, \synt{mixfix} denotes |
533 |
the usual parenthesized mixfix notation, and \synt{typefree} denotes fixed type |
|
534 |
variable (@{typ 'a}, @{typ 'b}, \ldots) \cite{isabelle-isar-ref}. |
|
52822 | 535 |
|
52827 | 536 |
The optional names preceding the type variables allow to override the default |
55705 | 537 |
names of the set functions (@{text set1_t}, \ldots, @{text setM_t}). Type |
57092 | 538 |
arguments can be marked as dead by entering ``@{text dead}'' in front of the |
539 |
type variable (e.g., ``@{text "(dead 'a)"}''); otherwise, they are live or dead |
|
55705 | 540 |
(and a set function is generated or not) depending on where they occur in the |
541 |
right-hand sides of the definition. Declaring a type argument as dead can speed |
|
542 |
up the type definition but will prevent any later (co)recursion through that |
|
543 |
type argument. |
|
544 |
||
53647 | 545 |
Inside a mutually recursive specification, all defined datatypes must |
546 |
mention exactly the same type variables in the same order. |
|
52822 | 547 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
548 |
@{rail \<open> |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
549 |
@{syntax_def dt_ctor}: (name ':')? name (@{syntax dt_ctor_arg} * ) mixfix? |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
550 |
\<close>} |
52824 | 551 |
|
53535 | 552 |
\medskip |
553 |
||
52827 | 554 |
\noindent |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
555 |
The main constituents of a constructor specification are the name of the |
52827 | 556 |
constructor and the list of its argument types. An optional discriminator name |
57091 | 557 |
can be supplied at the front to override the default, which is |
558 |
@{text "\<lambda>x. x = C\<^sub>j"} for nullary constructors and |
|
559 |
@{text t.is_C\<^sub>j} otherwise. |
|
52822 | 560 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
561 |
@{rail \<open> |
55472
990651bfc65b
updated docs to reflect the new 'free_constructors' syntax
blanchet
parents:
55468
diff
changeset
|
562 |
@{syntax_def dt_ctor_arg}: type | '(' name ':' type ')' |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
563 |
\<close>} |
52827 | 564 |
|
53535 | 565 |
\medskip |
566 |
||
52827 | 567 |
\noindent |
55474 | 568 |
The syntactic entity \synt{type} denotes a HOL type \cite{isabelle-isar-ref}. |
569 |
||
52827 | 570 |
In addition to the type of a constructor argument, it is possible to specify a |
571 |
name for the corresponding selector to override the default name |
|
53554 | 572 |
(@{text un_C\<^sub>ji}). The same selector names can be reused for several |
573 |
constructors as long as they share the same type. |
|
52822 | 574 |
*} |
575 |
||
53617 | 576 |
|
56644 | 577 |
subsubsection {* \keyw{datatype\_compat} |
578 |
\label{sssec:datatype-compat} *} |
|
53617 | 579 |
|
580 |
text {* |
|
53829 | 581 |
\begin{matharray}{rcl} |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
582 |
@{command_def "datatype_compat"} & : & @{text "local_theory \<rightarrow> local_theory"} |
53829 | 583 |
\end{matharray} |
584 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
585 |
@{rail \<open> |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
586 |
@@{command datatype_compat} (name +) |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
587 |
\<close>} |
53829 | 588 |
|
55351 | 589 |
\medskip |
590 |
||
53829 | 591 |
\noindent |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
592 |
The @{command datatype_compat} command registers new-style datatypes as |
55474 | 593 |
old-style datatypes. For example: |
53621 | 594 |
*} |
595 |
||
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
596 |
datatype_compat even_nat odd_nat |
53621 | 597 |
|
598 |
text {* \blankline *} |
|
599 |
||
53623 | 600 |
ML {* Datatype_Data.get_info @{theory} @{type_name even_nat} *} |
53621 | 601 |
|
602 |
text {* |
|
55474 | 603 |
The syntactic entity \synt{name} denotes an identifier \cite{isabelle-isar-ref}. |
604 |
||
605 |
The command is interesting because the old datatype package provides some |
|
56655 | 606 |
functionality that is not yet replicated in the new package, such as the |
607 |
integration with Quickcheck. |
|
55474 | 608 |
|
609 |
A few remarks concern nested recursive datatypes: |
|
53748 | 610 |
|
611 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
612 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
613 |
|
55871 | 614 |
\item The old-style, nested-as-mutual induction rule and recursor theorems are |
615 |
generated under their usual names but with ``@{text "compat_"}'' prefixed |
|
616 |
(e.g., @{text compat_tree.induct}). |
|
53748 | 617 |
|
618 |
\item All types through which recursion takes place must be new-style datatypes |
|
619 |
or the function type. In principle, it should be possible to support old-style |
|
55474 | 620 |
datatypes as well, but this has not been implemented yet (and there is currently |
621 |
no way to register old-style datatypes as new-style datatypes). |
|
54184 | 622 |
|
623 |
\item The recursor produced for types that recurse through functions has a |
|
56655 | 624 |
different signature than with the old package. This might affect the behavior of |
625 |
some third-party extensions. |
|
53748 | 626 |
\end{itemize} |
627 |
||
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
628 |
An alternative to @{command datatype_compat} is to use the old package's |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
629 |
\keyw{rep\_\allowbreak datatype} command. The associated proof obligations must then be |
53748 | 630 |
discharged manually. |
53617 | 631 |
*} |
632 |
||
633 |
||
634 |
subsection {* Generated Constants |
|
635 |
\label{ssec:datatype-generated-constants} *} |
|
636 |
||
637 |
text {* |
|
53623 | 638 |
Given a datatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
53617 | 639 |
with $m > 0$ live type variables and $n$ constructors |
640 |
@{text "t.C\<^sub>1"}, \ldots, @{text "t.C\<^sub>n"}, the |
|
641 |
following auxiliary constants are introduced: |
|
642 |
||
55353 | 643 |
\medskip |
644 |
||
645 |
\begin{tabular}{@ {}ll@ {}} |
|
646 |
Case combinator: & |
|
647 |
@{text t.case_t} (rendered using the familiar @{text case}--@{text of} syntax) \\ |
|
648 |
Discriminators: & |
|
649 |
@{text "t.is_C\<^sub>1"}$, \ldots, $@{text "t.is_C\<^sub>n"} \\ |
|
650 |
Selectors: & |
|
651 |
@{text t.un_C\<^sub>11}$, \ldots, $@{text t.un_C\<^sub>1k\<^sub>1} \\ |
|
652 |
& \quad\vdots \\ |
|
653 |
& @{text t.un_C\<^sub>n1}$, \ldots, $@{text t.un_C\<^sub>nk\<^sub>n} \\ |
|
654 |
Set functions: & |
|
56655 | 655 |
@{text t.set1_t}, \ldots, @{text t.setm_t} \\ |
55353 | 656 |
Map function: & |
657 |
@{text t.map_t} \\ |
|
658 |
Relator: & |
|
659 |
@{text t.rel_t} \\ |
|
660 |
Recursor: & |
|
56655 | 661 |
@{text t.rec_t} \\ |
662 |
Size function: & |
|
663 |
@{text t.size_t} |
|
55353 | 664 |
\end{tabular} |
665 |
||
666 |
\medskip |
|
53617 | 667 |
|
668 |
\noindent |
|
669 |
The case combinator, discriminators, and selectors are collectively called |
|
670 |
\emph{destructors}. The prefix ``@{text "t."}'' is an optional component of the |
|
54491 | 671 |
names and is normally hidden. |
56655 | 672 |
|
673 |
In addition to the above, the @{class size} class is instantiated to overload the |
|
674 |
@{const size} function based on @{text t.size_t}. |
|
53617 | 675 |
*} |
676 |
||
677 |
||
52840 | 678 |
subsection {* Generated Theorems |
679 |
\label{ssec:datatype-generated-theorems} *} |
|
52828 | 680 |
|
681 |
text {* |
|
53544 | 682 |
The characteristic theorems generated by @{command datatype_new} are grouped in |
53623 | 683 |
three broad categories: |
53535 | 684 |
|
53543 | 685 |
\begin{itemize} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
686 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
687 |
|
56655 | 688 |
\item The \emph{free constructor theorems} |
689 |
(Section~\ref{sssec:free-constructor-theorems}) are properties of the |
|
690 |
constructors and destructors that can be derived for any freely generated type. |
|
691 |
Internally, the derivation is performed by @{command free_constructors}. |
|
692 |
||
693 |
\item The \emph{functorial theorems} (Section~\ref{sssec:functorial-theorems}) |
|
694 |
are properties of datatypes related to their BNF nature. |
|
695 |
||
696 |
\item The \emph{inductive theorems} (Section~\ref{sssec:inductive-theorems}) |
|
697 |
are properties of datatypes related to their inductive nature. |
|
53552 | 698 |
|
53543 | 699 |
\end{itemize} |
53535 | 700 |
|
701 |
\noindent |
|
53542 | 702 |
The full list of named theorems can be obtained as usual by entering the |
53543 | 703 |
command \keyw{print\_theorems} immediately after the datatype definition. |
53542 | 704 |
This list normally excludes low-level theorems that reveal internal |
53552 | 705 |
constructions. To make these accessible, add the line |
53542 | 706 |
*} |
53535 | 707 |
|
53542 | 708 |
declare [[bnf_note_all]] |
709 |
(*<*) |
|
710 |
declare [[bnf_note_all = false]] |
|
711 |
(*>*) |
|
53535 | 712 |
|
53552 | 713 |
text {* |
714 |
\noindent |
|
715 |
to the top of the theory file. |
|
716 |
*} |
|
53535 | 717 |
|
53621 | 718 |
subsubsection {* Free Constructor Theorems |
719 |
\label{sssec:free-constructor-theorems} *} |
|
53535 | 720 |
|
53543 | 721 |
(*<*) |
53837 | 722 |
consts nonnull :: 'a |
53543 | 723 |
(*>*) |
724 |
||
53535 | 725 |
text {* |
54621 | 726 |
The free constructor theorems are partitioned in three subgroups. The first |
727 |
subgroup of properties is concerned with the constructors. They are listed below |
|
728 |
for @{typ "'a list"}: |
|
53543 | 729 |
|
53552 | 730 |
\begin{indentblock} |
53543 | 731 |
\begin{description} |
53544 | 732 |
|
53642 | 733 |
\item[@{text "t."}\hthm{inject} @{text "[iff, induct_simp]"}\rm:] ~ \\ |
53544 | 734 |
@{thm list.inject[no_vars]} |
735 |
||
53642 | 736 |
\item[@{text "t."}\hthm{distinct} @{text "[simp, induct_simp]"}\rm:] ~ \\ |
53543 | 737 |
@{thm list.distinct(1)[no_vars]} \\ |
738 |
@{thm list.distinct(2)[no_vars]} |
|
739 |
||
53642 | 740 |
\item[@{text "t."}\hthm{exhaust} @{text "[cases t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 741 |
@{thm list.exhaust[no_vars]} |
742 |
||
53642 | 743 |
\item[@{text "t."}\hthm{nchotomy}\rm:] ~ \\ |
53543 | 744 |
@{thm list.nchotomy[no_vars]} |
745 |
||
746 |
\end{description} |
|
53552 | 747 |
\end{indentblock} |
53543 | 748 |
|
749 |
\noindent |
|
53621 | 750 |
In addition, these nameless theorems are registered as safe elimination rules: |
751 |
||
752 |
\begin{indentblock} |
|
753 |
\begin{description} |
|
754 |
||
54386 | 755 |
\item[@{text "t."}\hthm{distinct {\upshape[}THEN notE}@{text ", elim!"}\hthm{\upshape]}\rm:] ~ \\ |
53621 | 756 |
@{thm list.distinct(1)[THEN notE, elim!, no_vars]} \\ |
757 |
@{thm list.distinct(2)[THEN notE, elim!, no_vars]} |
|
758 |
||
759 |
\end{description} |
|
760 |
\end{indentblock} |
|
761 |
||
762 |
\noindent |
|
53543 | 763 |
The next subgroup is concerned with the case combinator: |
764 |
||
53552 | 765 |
\begin{indentblock} |
53543 | 766 |
\begin{description} |
53544 | 767 |
|
53798 | 768 |
\item[@{text "t."}\hthm{case} @{text "[simp, code]"}\rm:] ~ \\ |
53543 | 769 |
@{thm list.case(1)[no_vars]} \\ |
770 |
@{thm list.case(2)[no_vars]} |
|
771 |
||
55398 | 772 |
\item[@{text "t."}\hthm{case\_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
53543 | 773 |
@{thm list.case_cong[no_vars]} |
774 |
||
53642 | 775 |
\item[@{text "t."}\hthm{weak\_case\_cong} @{text "[cong]"}\rm:] ~ \\ |
53543 | 776 |
@{thm list.weak_case_cong[no_vars]} |
777 |
||
53642 | 778 |
\item[@{text "t."}\hthm{split}\rm:] ~ \\ |
53543 | 779 |
@{thm list.split[no_vars]} |
780 |
||
53642 | 781 |
\item[@{text "t."}\hthm{split\_asm}\rm:] ~ \\ |
53543 | 782 |
@{thm list.split_asm[no_vars]} |
783 |
||
53544 | 784 |
\item[@{text "t."}\hthm{splits} = @{text "split split_asm"}] |
53543 | 785 |
|
786 |
\end{description} |
|
53552 | 787 |
\end{indentblock} |
53543 | 788 |
|
789 |
\noindent |
|
54621 | 790 |
The third subgroup revolves around discriminators and selectors: |
53543 | 791 |
|
53552 | 792 |
\begin{indentblock} |
53543 | 793 |
\begin{description} |
53544 | 794 |
|
53694 | 795 |
\item[@{text "t."}\hthm{disc} @{text "[simp]"}\rm:] ~ \\ |
796 |
@{thm list.disc(1)[no_vars]} \\ |
|
797 |
@{thm list.disc(2)[no_vars]} |
|
798 |
||
53703 | 799 |
\item[@{text "t."}\hthm{discI}\rm:] ~ \\ |
800 |
@{thm list.discI(1)[no_vars]} \\ |
|
801 |
@{thm list.discI(2)[no_vars]} |
|
802 |
||
53805 | 803 |
\item[@{text "t."}\hthm{sel} @{text "[simp, code]"}\rm:] ~ \\ |
53694 | 804 |
@{thm list.sel(1)[no_vars]} \\ |
805 |
@{thm list.sel(2)[no_vars]} |
|
53543 | 806 |
|
53642 | 807 |
\item[@{text "t."}\hthm{collapse} @{text "[simp]"}\rm:] ~ \\ |
53543 | 808 |
@{thm list.collapse(1)[no_vars]} \\ |
809 |
@{thm list.collapse(2)[no_vars]} |
|
810 |
||
53837 | 811 |
\item[@{text "t."}\hthm{disc\_exclude} @{text "[dest]"}\rm:] ~ \\ |
53543 | 812 |
These properties are missing for @{typ "'a list"} because there is only one |
813 |
proper discriminator. Had the datatype been introduced with a second |
|
53837 | 814 |
discriminator called @{const nonnull}, they would have read thusly: \\[\jot] |
815 |
@{prop "null list \<Longrightarrow> \<not> nonnull list"} \\ |
|
816 |
@{prop "nonnull list \<Longrightarrow> \<not> null list"} |
|
53543 | 817 |
|
53642 | 818 |
\item[@{text "t."}\hthm{disc\_exhaust} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 819 |
@{thm list.disc_exhaust[no_vars]} |
820 |
||
53916 | 821 |
\item[@{text "t."}\hthm{sel\_exhaust} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
822 |
@{thm list.sel_exhaust[no_vars]} |
|
823 |
||
53642 | 824 |
\item[@{text "t."}\hthm{expand}\rm:] ~ \\ |
53543 | 825 |
@{thm list.expand[no_vars]} |
826 |
||
53917 | 827 |
\item[@{text "t."}\hthm{sel\_split}\rm:] ~ \\ |
828 |
@{thm list.sel_split[no_vars]} |
|
829 |
||
830 |
\item[@{text "t."}\hthm{sel\_split\_asm}\rm:] ~ \\ |
|
831 |
@{thm list.sel_split_asm[no_vars]} |
|
832 |
||
54491 | 833 |
\item[@{text "t."}\hthm{case\_eq\_if}\rm:] ~ \\ |
834 |
@{thm list.case_eq_if[no_vars]} |
|
53543 | 835 |
|
836 |
\end{description} |
|
53552 | 837 |
\end{indentblock} |
54152 | 838 |
|
839 |
\noindent |
|
840 |
In addition, equational versions of @{text t.disc} are registered with the @{text "[code]"} |
|
841 |
attribute. |
|
53552 | 842 |
*} |
843 |
||
844 |
||
53621 | 845 |
subsubsection {* Functorial Theorems |
846 |
\label{sssec:functorial-theorems} *} |
|
53552 | 847 |
|
848 |
text {* |
|
54621 | 849 |
The functorial theorems are partitioned in two subgroups. The first subgroup |
56992 | 850 |
consists of properties involving the constructors or the destructors and either |
851 |
a set function, the map function, or the relator: |
|
53552 | 852 |
|
853 |
\begin{indentblock} |
|
854 |
\begin{description} |
|
855 |
||
53798 | 856 |
\item[@{text "t."}\hthm{set} @{text "[simp, code]"}\rm:] ~ \\ |
53694 | 857 |
@{thm list.set(1)[no_vars]} \\ |
858 |
@{thm list.set(2)[no_vars]} |
|
53552 | 859 |
|
56992 | 860 |
\item[@{text "t."}\hthm{set\_empty}\rm:] ~ \\ |
861 |
@{thm list.set_empty[no_vars]} |
|
862 |
||
57153 | 863 |
\item[@{text "t."}\hthm{sel\_set}\rm:] ~ \\ |
864 |
@{thm list.sel_set[no_vars]} |
|
865 |
||
53798 | 866 |
\item[@{text "t."}\hthm{map} @{text "[simp, code]"}\rm:] ~ \\ |
53552 | 867 |
@{thm list.map(1)[no_vars]} \\ |
868 |
@{thm list.map(2)[no_vars]} |
|
869 |
||
56992 | 870 |
\item[@{text "t."}\hthm{disc\_map\_iff} @{text "[simp]"}\rm:] ~ \\ |
871 |
@{thm list.disc_map_iff[no_vars]} |
|
872 |
||
57047 | 873 |
\item[@{text "t."}\hthm{sel\_map}\rm:] ~ \\ |
874 |
@{thm list.sel_map[no_vars]} |
|
875 |
||
54146 | 876 |
\item[@{text "t."}\hthm{rel\_inject} @{text "[simp]"}\rm:] ~ \\ |
53552 | 877 |
@{thm list.rel_inject(1)[no_vars]} \\ |
878 |
@{thm list.rel_inject(2)[no_vars]} |
|
879 |
||
57494 | 880 |
\item[@{text "t."}\hthm{rel\_intros}\rm:] ~ \\ |
881 |
@{thm list.rel_intros(1)[no_vars]} \\ |
|
882 |
@{thm list.rel_intros(2)[no_vars]} |
|
883 |
||
54146 | 884 |
\item[@{text "t."}\hthm{rel\_distinct} @{text "[simp]"}\rm:] ~ \\ |
53552 | 885 |
@{thm list.rel_distinct(1)[no_vars]} \\ |
886 |
@{thm list.rel_distinct(2)[no_vars]} |
|
887 |
||
888 |
\end{description} |
|
889 |
\end{indentblock} |
|
54146 | 890 |
|
891 |
\noindent |
|
892 |
In addition, equational versions of @{text t.rel_inject} and @{text |
|
893 |
rel_distinct} are registered with the @{text "[code]"} attribute. |
|
54621 | 894 |
|
895 |
The second subgroup consists of more abstract properties of the set functions, |
|
896 |
the map function, and the relator: |
|
897 |
||
898 |
\begin{indentblock} |
|
899 |
\begin{description} |
|
900 |
||
56992 | 901 |
\item[@{text "t."}\hthm{set\_map}\rm:] ~ \\ |
902 |
@{thm list.set_map[no_vars]} |
|
903 |
||
54621 | 904 |
\item[@{text "t."}\hthm{map\_comp}\rm:] ~ \\ |
905 |
@{thm list.map_cong0[no_vars]} |
|
906 |
||
54624
36301c99ed26
revert making 'map_cong' a 'cong' -- it breaks too many proofs in the AFP
blanchet
parents:
54621
diff
changeset
|
907 |
\item[@{text "t."}\hthm{map\_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
54621 | 908 |
@{thm list.map_cong[no_vars]} |
909 |
||
910 |
\item[@{text "t."}\hthm{map\_id}\rm:] ~ \\ |
|
911 |
@{thm list.map_id[no_vars]} |
|
912 |
||
56955 | 913 |
\item[@{text "t."}\hthm{map\_id0}\rm:] ~ \\ |
914 |
@{thm list.map_id0[no_vars]} |
|
915 |
||
56904 | 916 |
\item[@{text "t."}\hthm{map\_ident}\rm:] ~ \\ |
917 |
@{thm list.map_ident[no_vars]} |
|
918 |
||
54621 | 919 |
\item[@{text "t."}\hthm{rel\_compp}\rm:] ~ \\ |
920 |
@{thm list.rel_compp[no_vars]} |
|
921 |
||
922 |
\item[@{text "t."}\hthm{rel\_conversep}\rm:] ~ \\ |
|
923 |
@{thm list.rel_conversep[no_vars]} |
|
924 |
||
925 |
\item[@{text "t."}\hthm{rel\_eq}\rm:] ~ \\ |
|
926 |
@{thm list.rel_eq[no_vars]} |
|
927 |
||
928 |
\item[@{text "t."}\hthm{rel\_flip}\rm:] ~ \\ |
|
929 |
@{thm list.rel_flip[no_vars]} |
|
930 |
||
931 |
\item[@{text "t."}\hthm{rel\_mono}\rm:] ~ \\ |
|
932 |
@{thm list.rel_mono[no_vars]} |
|
933 |
||
934 |
\end{description} |
|
935 |
\end{indentblock} |
|
53535 | 936 |
*} |
937 |
||
938 |
||
53621 | 939 |
subsubsection {* Inductive Theorems |
940 |
\label{sssec:inductive-theorems} *} |
|
53535 | 941 |
|
942 |
text {* |
|
53623 | 943 |
The inductive theorems are as follows: |
53544 | 944 |
|
53552 | 945 |
\begin{indentblock} |
53544 | 946 |
\begin{description} |
947 |
||
57304 | 948 |
\item[@{text "t."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n, induct t]"}\rm:] ~ \\ |
53544 | 949 |
@{thm list.induct[no_vars]} |
950 |
||
53642 | 951 |
\item[@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53544 | 952 |
Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
953 |
prove $m$ properties simultaneously. |
|
52828 | 954 |
|
57472 | 955 |
\item[@{text "t."}\hthm{rel\_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n, induct pred]"}\rm:] ~ \\ |
956 |
@{thm list.rel_induct[no_vars]} |
|
957 |
||
958 |
\item[@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel\_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
|
959 |
Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
|
960 |
prove $m$ properties simultaneously. |
|
961 |
||
53798 | 962 |
\item[@{text "t."}\hthm{rec} @{text "[simp, code]"}\rm:] ~ \\ |
53544 | 963 |
@{thm list.rec(1)[no_vars]} \\ |
964 |
@{thm list.rec(2)[no_vars]} |
|
965 |
||
56655 | 966 |
\item[@{text "t."}\hthm{rec\_o\_map}\rm:] ~ \\ |
967 |
@{thm list.rec_o_map[no_vars]} |
|
968 |
||
969 |
\item[@{text "t."}\hthm{size} @{text "[simp, code]"}\rm:] ~ \\ |
|
970 |
@{thm list.size(1)[no_vars]} \\ |
|
971 |
@{thm list.size(2)[no_vars]} \\ |
|
972 |
@{thm list.size(3)[no_vars]} \\ |
|
973 |
@{thm list.size(4)[no_vars]} |
|
974 |
||
975 |
\item[@{text "t."}\hthm{size\_o\_map}\rm:] ~ \\ |
|
976 |
@{thm list.size_o_map[no_vars]} |
|
977 |
||
53544 | 978 |
\end{description} |
53552 | 979 |
\end{indentblock} |
53544 | 980 |
|
981 |
\noindent |
|
982 |
For convenience, @{command datatype_new} also provides the following collection: |
|
983 |
||
53552 | 984 |
\begin{indentblock} |
53544 | 985 |
\begin{description} |
986 |
||
55871 | 987 |
\item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.rec} @{text t.map} @{text t.rel_inject}] ~ \\ |
53694 | 988 |
@{text t.rel_distinct} @{text t.set} |
53544 | 989 |
|
990 |
\end{description} |
|
53552 | 991 |
\end{indentblock} |
52828 | 992 |
*} |
993 |
||
52794 | 994 |
|
52827 | 995 |
subsection {* Compatibility Issues |
52824 | 996 |
\label{ssec:datatype-compatibility-issues} *} |
52794 | 997 |
|
52828 | 998 |
text {* |
53997 | 999 |
The command @{command datatype_new} has been designed to be highly compatible |
1000 |
with the old \keyw{datatype}, to ease migration. There are nonetheless a few |
|
53647 | 1001 |
incompatibilities that may arise when porting to the new package: |
1002 |
||
1003 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1004 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1005 |
|
53647 | 1006 |
\item \emph{The Standard ML interfaces are different.} Tools and extensions |
1007 |
written to call the old ML interfaces will need to be adapted to the new |
|
56655 | 1008 |
interfaces. This concerns Quickcheck in particular. Whenever possible, it is |
1009 |
recommended to use @{command datatype_compat} to register new-style datatypes |
|
1010 |
as old-style datatypes. |
|
53647 | 1011 |
|
56644 | 1012 |
\item \emph{The constants @{text t_case}, @{text t_rec}, and @{text t_size} are |
1013 |
now called @{text case_t}, @{text rec_t}, and @{text size_t}.} |
|
54537 | 1014 |
|
1015 |
\item \emph{The recursor @{text rec_t} has a different signature for nested |
|
54185 | 1016 |
recursive datatypes.} In the old package, nested recursion through non-functions |
1017 |
was internally reduced to mutual recursion. This reduction was visible in the |
|
1018 |
type of the recursor, used by \keyw{primrec}. Recursion through functions was |
|
1019 |
handled specially. In the new package, nested recursion (for functions and |
|
1020 |
non-functions) is handled in a more modular fashion. The old-style recursor can |
|
56655 | 1021 |
be generated on demand using @{command primrec} if the recursion is via |
1022 |
new-style datatypes, as explained in |
|
1023 |
Section~\ref{sssec:primrec-nested-as-mutual-recursion}. |
|
53647 | 1024 |
|
54287 | 1025 |
\item \emph{Accordingly, the induction rule is different for nested recursive |
1026 |
datatypes.} Again, the old-style induction rule can be generated on demand using |
|
56655 | 1027 |
@{command primrec} if the recursion is via new-style datatypes, as explained in |
1028 |
Section~\ref{sssec:primrec-nested-as-mutual-recursion}. |
|
52828 | 1029 |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
1030 |
\item \emph{The internal constructions are completely different.} Proof texts |
53647 | 1031 |
that unfold the definition of constants introduced by \keyw{datatype} will be |
1032 |
difficult to port. |
|
1033 |
||
56644 | 1034 |
\item \emph{Some theorems have different names.} |
55641
5b466efedd2c
renamed 'recs' and 'cases' theorems 'rec' and 'case' in old datatype package, for consistency with new package
blanchet
parents:
55531
diff
changeset
|
1035 |
For non-mutually recursive datatypes, |
5b466efedd2c
renamed 'recs' and 'cases' theorems 'rec' and 'case' in old datatype package, for consistency with new package
blanchet
parents:
55531
diff
changeset
|
1036 |
the alias @{text t.inducts} for @{text t.induct} is no longer generated. |
53647 | 1037 |
For $m > 1$ mutually recursive datatypes, |
53997 | 1038 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m.inducts(i)"} has been renamed |
56644 | 1039 |
@{text "t\<^sub>i.induct"} for each @{text "i \<in> {1, \<dots>, t}"}, and similarly the |
1040 |
collection @{text "t\<^sub>1_\<dots>_t\<^sub>m.size"} has been divided into @{text "t\<^sub>1.size"}, |
|
1041 |
\ldots, @{text "t\<^sub>m.size"}. |
|
53647 | 1042 |
|
1043 |
\item \emph{The @{text t.simps} collection has been extended.} |
|
1044 |
Previously available theorems are available at the same index. |
|
1045 |
||
1046 |
\item \emph{Variables in generated properties have different names.} This is |
|
1047 |
rarely an issue, except in proof texts that refer to variable names in the |
|
1048 |
@{text "[where \<dots>]"} attribute. The solution is to use the more robust |
|
1049 |
@{text "[of \<dots>]"} syntax. |
|
1050 |
\end{itemize} |
|
1051 |
||
1052 |
In the other direction, there is currently no way to register old-style |
|
1053 |
datatypes as new-style datatypes. If the goal is to define new-style datatypes |
|
1054 |
with nested recursion through old-style datatypes, the old-style |
|
1055 |
datatypes can be registered as a BNF |
|
55351 | 1056 |
(Section~\ref{sec:introducing-bounded-natural-functors}). If the goal is |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
1057 |
to derive discriminators and selectors, this can be achieved using |
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
1058 |
@{command free_constructors} |
53647 | 1059 |
(Section~\ref{sec:deriving-destructors-and-theorems-for-free-constructors}). |
52828 | 1060 |
*} |
1061 |
||
52792 | 1062 |
|
52827 | 1063 |
section {* Defining Recursive Functions |
52805 | 1064 |
\label{sec:defining-recursive-functions} *} |
1065 |
||
1066 |
text {* |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1067 |
Recursive functions over datatypes can be specified using the @{command primrec} |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1068 |
command, which supports primitive recursion, or using the more general |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1069 |
\keyw{fun} and \keyw{function} commands. Here, the focus is on |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1070 |
@{command primrec}; the other two commands are described in a separate |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1071 |
tutorial \cite{isabelle-function}. |
52828 | 1072 |
|
53621 | 1073 |
%%% TODO: partial_function |
52805 | 1074 |
*} |
52792 | 1075 |
|
52805 | 1076 |
|
53617 | 1077 |
subsection {* Introductory Examples |
1078 |
\label{ssec:primrec-introductory-examples} *} |
|
52828 | 1079 |
|
53646 | 1080 |
text {* |
1081 |
Primitive recursion is illustrated through concrete examples based on the |
|
1082 |
datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More |
|
55075 | 1083 |
examples can be found in the directory \verb|~~/src/HOL/BNF_Examples|. |
53646 | 1084 |
*} |
1085 |
||
53621 | 1086 |
|
1087 |
subsubsection {* Nonrecursive Types |
|
1088 |
\label{sssec:primrec-nonrecursive-types} *} |
|
52828 | 1089 |
|
52841 | 1090 |
text {* |
53621 | 1091 |
Primitive recursion removes one layer of constructors on the left-hand side in |
1092 |
each equation. For example: |
|
52841 | 1093 |
*} |
1094 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1095 |
primrec bool_of_trool :: "trool \<Rightarrow> bool" where |
53621 | 1096 |
"bool_of_trool Faalse \<longleftrightarrow> False" | |
1097 |
"bool_of_trool Truue \<longleftrightarrow> True" |
|
52841 | 1098 |
|
53621 | 1099 |
text {* \blankline *} |
52841 | 1100 |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1101 |
primrec the_list :: "'a option \<Rightarrow> 'a list" where |
53025 | 1102 |
"the_list None = []" | |
1103 |
"the_list (Some a) = [a]" |
|
52841 | 1104 |
|
53621 | 1105 |
text {* \blankline *} |
1106 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1107 |
primrec the_default :: "'a \<Rightarrow> 'a option \<Rightarrow> 'a" where |
53025 | 1108 |
"the_default d None = d" | |
1109 |
"the_default _ (Some a) = a" |
|
52843 | 1110 |
|
53621 | 1111 |
text {* \blankline *} |
1112 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1113 |
primrec mirrror :: "('a, 'b, 'c) triple \<Rightarrow> ('c, 'b, 'a) triple" where |
52841 | 1114 |
"mirrror (Triple a b c) = Triple c b a" |
1115 |
||
53621 | 1116 |
text {* |
1117 |
\noindent |
|
1118 |
The equations can be specified in any order, and it is acceptable to leave out |
|
1119 |
some cases, which are then unspecified. Pattern matching on the left-hand side |
|
1120 |
is restricted to a single datatype, which must correspond to the same argument |
|
1121 |
in all equations. |
|
1122 |
*} |
|
52828 | 1123 |
|
53621 | 1124 |
|
1125 |
subsubsection {* Simple Recursion |
|
1126 |
\label{sssec:primrec-simple-recursion} *} |
|
52828 | 1127 |
|
52841 | 1128 |
text {* |
53621 | 1129 |
For simple recursive types, recursive calls on a constructor argument are |
1130 |
allowed on the right-hand side: |
|
52841 | 1131 |
*} |
1132 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1133 |
primrec replicate :: "nat \<Rightarrow> 'a \<Rightarrow> 'a list" where |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1134 |
"replicate Zero _ = []" | |
53644 | 1135 |
"replicate (Suc n) x = x # replicate n x" |
52841 | 1136 |
|
53621 | 1137 |
text {* \blankline *} |
52843 | 1138 |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1139 |
primrec at :: "'a list \<Rightarrow> nat \<Rightarrow> 'a" where |
53644 | 1140 |
"at (x # xs) j = |
52843 | 1141 |
(case j of |
53644 | 1142 |
Zero \<Rightarrow> x |
1143 |
| Suc j' \<Rightarrow> at xs j')" |
|
52843 | 1144 |
|
53621 | 1145 |
text {* \blankline *} |
1146 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1147 |
primrec (*<*)(in early) (*>*)tfold :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> ('a, 'b) tlist \<Rightarrow> 'b" where |
53644 | 1148 |
"tfold _ (TNil y) = y" | |
1149 |
"tfold f (TCons x xs) = f x (tfold f xs)" |
|
52841 | 1150 |
|
53025 | 1151 |
text {* |
53621 | 1152 |
\noindent |
54402 | 1153 |
Pattern matching is only available for the argument on which the recursion takes |
1154 |
place. Fortunately, it is easy to generate pattern-maching equations using the |
|
1155 |
\keyw{simps\_of\_case} command provided by the theory |
|
55290 | 1156 |
\verb|~~/src/HOL/|\allowbreak\verb|Library/|\allowbreak\verb|Simps_Case_Conv|. |
54402 | 1157 |
*} |
1158 |
||
1159 |
simps_of_case at_simps: at.simps |
|
1160 |
||
1161 |
text {* |
|
1162 |
This generates the lemma collection @{thm [source] at_simps}: |
|
1163 |
% |
|
1164 |
\[@{thm at_simps(1)[no_vars]} |
|
1165 |
\qquad @{thm at_simps(2)[no_vars]}\] |
|
1166 |
% |
|
54184 | 1167 |
The next example is defined using \keyw{fun} to escape the syntactic |
55254 | 1168 |
restrictions imposed on primitively recursive functions. The |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
1169 |
@{command datatype_compat} command is needed to register new-style datatypes |
54184 | 1170 |
for use with \keyw{fun} and \keyw{function} |
56644 | 1171 |
(Section~\ref{sssec:datatype-compat}): |
53025 | 1172 |
*} |
52828 | 1173 |
|
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
1174 |
datatype_compat nat |
53621 | 1175 |
|
1176 |
text {* \blankline *} |
|
1177 |
||
1178 |
fun at_least_two :: "nat \<Rightarrow> bool" where |
|
1179 |
"at_least_two (Suc (Suc _)) \<longleftrightarrow> True" | |
|
1180 |
"at_least_two _ \<longleftrightarrow> False" |
|
1181 |
||
1182 |
||
1183 |
subsubsection {* Mutual Recursion |
|
1184 |
\label{sssec:primrec-mutual-recursion} *} |
|
52828 | 1185 |
|
52841 | 1186 |
text {* |
53621 | 1187 |
The syntax for mutually recursive functions over mutually recursive datatypes |
1188 |
is straightforward: |
|
52841 | 1189 |
*} |
1190 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1191 |
primrec |
53623 | 1192 |
nat_of_even_nat :: "even_nat \<Rightarrow> nat" and |
1193 |
nat_of_odd_nat :: "odd_nat \<Rightarrow> nat" |
|
52841 | 1194 |
where |
53623 | 1195 |
"nat_of_even_nat Even_Zero = Zero" | |
1196 |
"nat_of_even_nat (Even_Suc n) = Suc (nat_of_odd_nat n)" | |
|
1197 |
"nat_of_odd_nat (Odd_Suc n) = Suc (nat_of_even_nat n)" |
|
52841 | 1198 |
|
53752 | 1199 |
text {* \blankline *} |
1200 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1201 |
primrec |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1202 |
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
|
1203 |
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
|
1204 |
eval\<^sub>f :: "('a \<Rightarrow> int) \<Rightarrow> ('b \<Rightarrow> int) \<Rightarrow> ('a, 'b) fct \<Rightarrow> int" |
52841 | 1205 |
where |
1206 |
"eval\<^sub>e \<gamma> \<xi> (Term t) = eval\<^sub>t \<gamma> \<xi> t" | |
|
1207 |
"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
|
1208 |
"eval\<^sub>t \<gamma> \<xi> (Factor f) = eval\<^sub>f \<gamma> \<xi> f" | |
52841 | 1209 |
"eval\<^sub>t \<gamma> \<xi> (Prod f t) = eval\<^sub>f \<gamma> \<xi> f + eval\<^sub>t \<gamma> \<xi> t" | |
1210 |
"eval\<^sub>f \<gamma> _ (Const a) = \<gamma> a" | |
|
1211 |
"eval\<^sub>f _ \<xi> (Var b) = \<xi> b" | |
|
1212 |
"eval\<^sub>f \<gamma> \<xi> (Expr e) = eval\<^sub>e \<gamma> \<xi> e" |
|
1213 |
||
53621 | 1214 |
text {* |
1215 |
\noindent |
|
53647 | 1216 |
Mutual recursion is possible within a single type, using \keyw{fun}: |
53621 | 1217 |
*} |
52828 | 1218 |
|
53621 | 1219 |
fun |
1220 |
even :: "nat \<Rightarrow> bool" and |
|
1221 |
odd :: "nat \<Rightarrow> bool" |
|
1222 |
where |
|
1223 |
"even Zero = True" | |
|
1224 |
"even (Suc n) = odd n" | |
|
1225 |
"odd Zero = False" | |
|
1226 |
"odd (Suc n) = even n" |
|
1227 |
||
1228 |
||
1229 |
subsubsection {* Nested Recursion |
|
1230 |
\label{sssec:primrec-nested-recursion} *} |
|
1231 |
||
1232 |
text {* |
|
1233 |
In a departure from the old datatype package, nested recursion is normally |
|
1234 |
handled via the map functions of the nesting type constructors. For example, |
|
1235 |
recursive calls are lifted to lists using @{const map}: |
|
1236 |
*} |
|
52828 | 1237 |
|
52843 | 1238 |
(*<*) |
53644 | 1239 |
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 | 1240 |
(*>*) |
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1241 |
primrec at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" where |
53028 | 1242 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
52843 | 1243 |
(case js of |
1244 |
[] \<Rightarrow> a |
|
53028 | 1245 |
| j # js' \<Rightarrow> at (map (\<lambda>t. at\<^sub>f\<^sub>f t js') ts) j)" |
52843 | 1246 |
|
53025 | 1247 |
text {* |
53647 | 1248 |
\noindent |
53621 | 1249 |
The next example features recursion through the @{text option} type. Although |
53623 | 1250 |
@{text option} is not a new-style datatype, it is registered as a BNF with the |
54491 | 1251 |
map function @{const map_option}: |
53025 | 1252 |
*} |
52843 | 1253 |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1254 |
primrec (*<*)(in early) (*>*)sum_btree :: "('a\<Colon>{zero,plus}) btree \<Rightarrow> 'a" where |
52843 | 1255 |
"sum_btree (BNode a lt rt) = |
54491 | 1256 |
a + the_default 0 (map_option sum_btree lt) + |
1257 |
the_default 0 (map_option sum_btree rt)" |
|
52843 | 1258 |
|
53136 | 1259 |
text {* |
53621 | 1260 |
\noindent |
1261 |
The same principle applies for arbitrary type constructors through which |
|
1262 |
recursion is possible. Notably, the map function for the function type |
|
1263 |
(@{text \<Rightarrow>}) is simply composition (@{text "op \<circ>"}): |
|
53136 | 1264 |
*} |
52828 | 1265 |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1266 |
primrec (*<*)(in early) (*>*)relabel_ft :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
54182 | 1267 |
"relabel_ft f (FTLeaf x) = FTLeaf (f x)" | |
1268 |
"relabel_ft f (FTNode g) = FTNode (relabel_ft f \<circ> g)" |
|
1269 |
||
1270 |
text {* |
|
1271 |
\noindent |
|
1272 |
For convenience, recursion through functions can also be expressed using |
|
1273 |
$\lambda$-abstractions and function application rather than through composition. |
|
1274 |
For example: |
|
1275 |
*} |
|
1276 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1277 |
primrec relabel_ft :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
54182 | 1278 |
"relabel_ft f (FTLeaf x) = FTLeaf (f x)" | |
1279 |
"relabel_ft f (FTNode g) = FTNode (\<lambda>x. relabel_ft f (g x))" |
|
52828 | 1280 |
|
54183 | 1281 |
text {* \blankline *} |
1282 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1283 |
primrec subtree_ft :: "'a \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
54183 | 1284 |
"subtree_ft x (FTNode g) = g x" |
1285 |
||
52843 | 1286 |
text {* |
53621 | 1287 |
\noindent |
54182 | 1288 |
For recursion through curried $n$-ary functions, $n$ applications of |
1289 |
@{term "op \<circ>"} are necessary. The examples below illustrate the case where |
|
1290 |
$n = 2$: |
|
53621 | 1291 |
*} |
1292 |
||
54182 | 1293 |
datatype_new 'a ftree2 = FTLeaf2 'a | FTNode2 "'a \<Rightarrow> 'a \<Rightarrow> 'a ftree2" |
1294 |
||
1295 |
text {* \blankline *} |
|
1296 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1297 |
primrec (*<*)(in early) (*>*)relabel_ft2 :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree2 \<Rightarrow> 'a ftree2" where |
54182 | 1298 |
"relabel_ft2 f (FTLeaf2 x) = FTLeaf2 (f x)" | |
1299 |
"relabel_ft2 f (FTNode2 g) = FTNode2 (op \<circ> (op \<circ> (relabel_ft2 f)) g)" |
|
1300 |
||
1301 |
text {* \blankline *} |
|
1302 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1303 |
primrec relabel_ft2 :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree2 \<Rightarrow> 'a ftree2" where |
54182 | 1304 |
"relabel_ft2 f (FTLeaf2 x) = FTLeaf2 (f x)" | |
1305 |
"relabel_ft2 f (FTNode2 g) = FTNode2 (\<lambda>x y. relabel_ft2 f (g x y))" |
|
54031 | 1306 |
|
54183 | 1307 |
text {* \blankline *} |
1308 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1309 |
primrec subtree_ft2 :: "'a \<Rightarrow> 'a \<Rightarrow> 'a ftree2 \<Rightarrow> 'a ftree2" where |
54183 | 1310 |
"subtree_ft2 x y (FTNode2 g) = g x y" |
1311 |
||
53621 | 1312 |
|
1313 |
subsubsection {* Nested-as-Mutual Recursion |
|
53644 | 1314 |
\label{sssec:primrec-nested-as-mutual-recursion} *} |
53621 | 1315 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1316 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1317 |
locale n2m begin |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1318 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1319 |
|
53621 | 1320 |
text {* |
1321 |
For compatibility with the old package, but also because it is sometimes |
|
1322 |
convenient in its own right, it is possible to treat nested recursive datatypes |
|
1323 |
as mutually recursive ones if the recursion takes place though new-style |
|
1324 |
datatypes. For example: |
|
52843 | 1325 |
*} |
1326 |
||
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1327 |
primrec |
53647 | 1328 |
at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" and |
1329 |
ats\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f list \<Rightarrow> nat \<Rightarrow> nat list \<Rightarrow> 'a" |
|
52843 | 1330 |
where |
53647 | 1331 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
52843 | 1332 |
(case js of |
1333 |
[] \<Rightarrow> a |
|
53647 | 1334 |
| j # js' \<Rightarrow> ats\<^sub>f\<^sub>f ts j js')" | |
1335 |
"ats\<^sub>f\<^sub>f (t # ts) j = |
|
52843 | 1336 |
(case j of |
53647 | 1337 |
Zero \<Rightarrow> at\<^sub>f\<^sub>f t |
1338 |
| Suc j' \<Rightarrow> ats\<^sub>f\<^sub>f ts j')" |
|
52843 | 1339 |
|
53647 | 1340 |
text {* |
1341 |
\noindent |
|
54287 | 1342 |
Appropriate induction rules are generated as |
54031 | 1343 |
@{thm [source] at\<^sub>f\<^sub>f.induct}, |
1344 |
@{thm [source] ats\<^sub>f\<^sub>f.induct}, and |
|
54287 | 1345 |
@{thm [source] at\<^sub>f\<^sub>f_ats\<^sub>f\<^sub>f.induct}. The |
1346 |
induction rules and the underlying recursors are generated on a per-need basis |
|
1347 |
and are kept in a cache to speed up subsequent definitions. |
|
53647 | 1348 |
|
1349 |
Here is a second example: |
|
1350 |
*} |
|
53621 | 1351 |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1352 |
primrec |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1353 |
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
|
1354 |
sum_btree_option :: "'a btree option \<Rightarrow> 'a" |
52843 | 1355 |
where |
1356 |
"sum_btree (BNode a lt rt) = |
|
53025 | 1357 |
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
|
1358 |
"sum_btree_option None = 0" | |
53025 | 1359 |
"sum_btree_option (Some t) = sum_btree t" |
52843 | 1360 |
|
1361 |
text {* |
|
53621 | 1362 |
% * can pretend a nested type is mutually recursive (if purely inductive) |
1363 |
% * avoids the higher-order map |
|
1364 |
% * e.g. |
|
1365 |
||
53617 | 1366 |
% * this can always be avoided; |
1367 |
% * e.g. in our previous example, we first mapped the recursive |
|
1368 |
% calls, then we used a generic at function to retrieve the result |
|
1369 |
% |
|
1370 |
% * there's no hard-and-fast rule of when to use one or the other, |
|
1371 |
% just like there's no rule when to use fold and when to use |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1372 |
% primrec |
53617 | 1373 |
% |
1374 |
% * higher-order approach, considering nesting as nesting, is more |
|
1375 |
% compositional -- e.g. we saw how we could reuse an existing polymorphic |
|
53647 | 1376 |
% at or the_default, whereas @{const ats\<^sub>f\<^sub>f} is much more specific |
53617 | 1377 |
% |
1378 |
% * but: |
|
1379 |
% * is perhaps less intuitive, because it requires higher-order thinking |
|
1380 |
% * may seem inefficient, and indeed with the code generator the |
|
1381 |
% mutually recursive version might be nicer |
|
1382 |
% * is somewhat indirect -- must apply a map first, then compute a result |
|
1383 |
% (cannot mix) |
|
53647 | 1384 |
% * the auxiliary functions like @{const ats\<^sub>f\<^sub>f} are sometimes useful in own right |
53617 | 1385 |
% |
1386 |
% * impact on automation unclear |
|
1387 |
% |
|
52843 | 1388 |
*} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1389 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1390 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1391 |
(*>*) |
52843 | 1392 |
|
52824 | 1393 |
|
53617 | 1394 |
subsection {* Command Syntax |
1395 |
\label{ssec:primrec-command-syntax} *} |
|
1396 |
||
1397 |
||
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1398 |
subsubsection {* \keyw{primrec} |
53621 | 1399 |
\label{sssec:primrec-new} *} |
52828 | 1400 |
|
1401 |
text {* |
|
53829 | 1402 |
\begin{matharray}{rcl} |
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1403 |
@{command_def "primrec"} & : & @{text "local_theory \<rightarrow> local_theory"} |
53829 | 1404 |
\end{matharray} |
52794 | 1405 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1406 |
@{rail \<open> |
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1407 |
@@{command primrec} target? @{syntax pr_option}? fixes \<newline> |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1408 |
@'where' (@{syntax pr_equation} + '|') |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1409 |
; |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1410 |
@{syntax_def pr_option}: '(' 'nonexhaustive' ')' |
52840 | 1411 |
; |
53829 | 1412 |
@{syntax_def pr_equation}: thmdecl? prop |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1413 |
\<close>} |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1414 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1415 |
\medskip |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1416 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1417 |
\noindent |
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1418 |
The @{command primrec} command introduces a set of mutually recursive functions |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1419 |
over datatypes. |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1420 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1421 |
The syntactic entity \synt{target} can be used to specify a local context, |
55474 | 1422 |
\synt{fixes} denotes a list of names with optional type signatures, |
1423 |
\synt{thmdecl} denotes an optional name for the formula that follows, and |
|
1424 |
\synt{prop} denotes a HOL proposition \cite{isabelle-isar-ref}. |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1425 |
|
56124 | 1426 |
The optional target is optionally followed by the following option: |
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1427 |
|
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1428 |
\begin{itemize} |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1429 |
\setlength{\itemsep}{0pt} |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1430 |
|
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1431 |
\item |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1432 |
The @{text "nonexhaustive"} option indicates that the functions are not |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1433 |
necessarily specified for all constructors. It can be used to suppress the |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1434 |
warning that is normally emitted when some constructors are missing. |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1435 |
\end{itemize} |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1436 |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1437 |
%%% TODO: elaborate on format of the equations |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1438 |
%%% TODO: elaborate on mutual and nested-to-mutual |
52828 | 1439 |
*} |
1440 |
||
52840 | 1441 |
|
53619 | 1442 |
(* |
52840 | 1443 |
subsection {* Generated Theorems |
1444 |
\label{ssec:primrec-generated-theorems} *} |
|
52824 | 1445 |
|
52828 | 1446 |
text {* |
53617 | 1447 |
% * synthesized nonrecursive definition |
1448 |
% * user specification is rederived from it, exactly as entered |
|
1449 |
% |
|
1450 |
% * induct |
|
1451 |
% * mutualized |
|
1452 |
% * without some needless induction hypotheses if not used |
|
55871 | 1453 |
% * rec |
53617 | 1454 |
% * mutualized |
52828 | 1455 |
*} |
53619 | 1456 |
*) |
1457 |
||
52824 | 1458 |
|
52840 | 1459 |
subsection {* Recursive Default Values for Selectors |
53623 | 1460 |
\label{ssec:primrec-recursive-default-values-for-selectors} *} |
52827 | 1461 |
|
1462 |
text {* |
|
1463 |
A datatype selector @{text un_D} can have a default value for each constructor |
|
1464 |
on which it is not otherwise specified. Occasionally, it is useful to have the |
|
55354 | 1465 |
default value be defined recursively. This leads to a chicken-and-egg |
1466 |
situation, because the datatype is not introduced yet at the moment when the |
|
1467 |
selectors are introduced. Of course, we can always define the selectors |
|
1468 |
manually afterward, but we then have to state and prove all the characteristic |
|
1469 |
theorems ourselves instead of letting the package do it. |
|
1470 |
||
1471 |
Fortunately, there is a workaround that relies on overloading to relieve us |
|
1472 |
from the tedium of manual derivations: |
|
52827 | 1473 |
|
1474 |
\begin{enumerate} |
|
1475 |
\setlength{\itemsep}{0pt} |
|
1476 |
||
1477 |
\item |
|
1478 |
Introduce a fully unspecified constant @{text "un_D\<^sub>0 \<Colon> 'a"} using |
|
1479 |
@{keyword consts}. |
|
1480 |
||
1481 |
\item |
|
53535 | 1482 |
Define the datatype, specifying @{text "un_D\<^sub>0"} as the selector's default |
1483 |
value. |
|
52827 | 1484 |
|
1485 |
\item |
|
53535 | 1486 |
Define the behavior of @{text "un_D\<^sub>0"} on values of the newly introduced |
1487 |
datatype using the \keyw{overloading} command. |
|
52827 | 1488 |
|
1489 |
\item |
|
1490 |
Derive the desired equation on @{text un_D} from the characteristic equations |
|
1491 |
for @{text "un_D\<^sub>0"}. |
|
1492 |
\end{enumerate} |
|
1493 |
||
53619 | 1494 |
\noindent |
52827 | 1495 |
The following example illustrates this procedure: |
1496 |
*} |
|
1497 |
||
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1498 |
(*<*) |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1499 |
hide_const termi |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1500 |
(*>*) |
52827 | 1501 |
consts termi\<^sub>0 :: 'a |
1502 |
||
53619 | 1503 |
text {* \blankline *} |
1504 |
||
53491 | 1505 |
datatype_new ('a, 'b) tlist = |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1506 |
TNil (termi: 'b) |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1507 |
| TCons (thd: 'a) (ttl: "('a, 'b) tlist") |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1508 |
where |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1509 |
"ttl (TNil y) = TNil y" |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1510 |
| "termi (TCons _ xs) = termi\<^sub>0 xs" |
52827 | 1511 |
|
53619 | 1512 |
text {* \blankline *} |
1513 |
||
52827 | 1514 |
overloading |
53491 | 1515 |
termi\<^sub>0 \<equiv> "termi\<^sub>0 \<Colon> ('a, 'b) tlist \<Rightarrow> 'b" |
52827 | 1516 |
begin |
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1517 |
primrec termi\<^sub>0 :: "('a, 'b) tlist \<Rightarrow> 'b" where |
53621 | 1518 |
"termi\<^sub>0 (TNil y) = y" | |
1519 |
"termi\<^sub>0 (TCons x xs) = termi\<^sub>0 xs" |
|
52827 | 1520 |
end |
1521 |
||
53619 | 1522 |
text {* \blankline *} |
1523 |
||
55354 | 1524 |
lemma termi_TCons[simp]: "termi (TCons x xs) = termi xs" |
52827 | 1525 |
by (cases xs) auto |
1526 |
||
1527 |
||
52828 | 1528 |
subsection {* Compatibility Issues |
53617 | 1529 |
\label{ssec:primrec-compatibility-issues} *} |
52828 | 1530 |
|
1531 |
text {* |
|
55530
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1532 |
The command @{command primrec}'s behavior on new-style datatypes has been |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1533 |
designed to be highly compatible with that for old-style datatypes, to ease |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1534 |
migration. There is nonetheless at least one incompatibility that may arise when |
3dfb724db099
renamed 'primrec_new' to 'primrec', overriding the old command (which it still uses as a fallback for old-style datatypes)
blanchet
parents:
55474
diff
changeset
|
1535 |
porting to the new package: |
53997 | 1536 |
|
1537 |
\begin{itemize} |
|
1538 |
\setlength{\itemsep}{0pt} |
|
1539 |
||
54185 | 1540 |
\item \emph{Some theorems have different names.} |
53997 | 1541 |
For $m > 1$ mutually recursive functions, |
54023
cede3c1d2417
minor doc fix (there is no guarantee that the equations for a given f_i are contiguous in the collection)
blanchet
parents:
54014
diff
changeset
|
1542 |
@{text "f\<^sub>1_\<dots>_f\<^sub>m.simps"} has been broken down into separate |
cede3c1d2417
minor doc fix (there is no guarantee that the equations for a given f_i are contiguous in the collection)
blanchet
parents:
54014
diff
changeset
|
1543 |
subcollections @{text "f\<^sub>i.simps"}. |
53997 | 1544 |
\end{itemize} |
52828 | 1545 |
*} |
52794 | 1546 |
|
1547 |
||
52827 | 1548 |
section {* Defining Codatatypes |
52805 | 1549 |
\label{sec:defining-codatatypes} *} |
1550 |
||
1551 |
text {* |
|
53829 | 1552 |
Codatatypes can be specified using the @{command codatatype} command. The |
53623 | 1553 |
command is first illustrated through concrete examples featuring different |
1554 |
flavors of corecursion. More examples can be found in the directory |
|
53997 | 1555 |
\verb|~~/src/HOL/|\allowbreak\verb|BNF/Examples|. The |
1556 |
\emph{Archive of Formal Proofs} also includes some useful codatatypes, notably |
|
1557 |
for lazy lists \cite{lochbihler-2010}. |
|
52805 | 1558 |
*} |
52792 | 1559 |
|
52824 | 1560 |
|
53617 | 1561 |
subsection {* Introductory Examples |
1562 |
\label{ssec:codatatype-introductory-examples} *} |
|
52794 | 1563 |
|
53623 | 1564 |
|
1565 |
subsubsection {* Simple Corecursion |
|
1566 |
\label{sssec:codatatype-simple-corecursion} *} |
|
1567 |
||
52805 | 1568 |
text {* |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
1569 |
Noncorecursive codatatypes coincide with the corresponding datatypes, so they |
56947 | 1570 |
are rarely used in practice. \emph{Corecursive codatatypes} have the same syntax |
53623 | 1571 |
as recursive datatypes, except for the command name. For example, here is the |
1572 |
definition of lazy lists: |
|
1573 |
*} |
|
1574 |
||
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1575 |
codatatype (lset: 'a) llist = |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1576 |
lnull: LNil |
53623 | 1577 |
| LCons (lhd: 'a) (ltl: "'a llist") |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1578 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1579 |
map: lmap |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1580 |
rel: llist_all2 |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1581 |
where |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1582 |
"ltl LNil = LNil" |
53623 | 1583 |
|
1584 |
text {* |
|
1585 |
\noindent |
|
1586 |
Lazy lists can be infinite, such as @{text "LCons 0 (LCons 0 (\<dots>))"} and |
|
53647 | 1587 |
@{text "LCons 0 (LCons 1 (LCons 2 (\<dots>)))"}. Here is a related type, that of |
1588 |
infinite streams: |
|
1589 |
*} |
|
1590 |
||
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1591 |
codatatype (sset: 'a) stream = |
53647 | 1592 |
SCons (shd: 'a) (stl: "'a stream") |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1593 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1594 |
map: smap |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1595 |
rel: stream_all2 |
53647 | 1596 |
|
1597 |
text {* |
|
1598 |
\noindent |
|
1599 |
Another interesting type that can |
|
53623 | 1600 |
be defined as a codatatype is that of the extended natural numbers: |
1601 |
*} |
|
1602 |
||
53644 | 1603 |
codatatype enat = EZero | ESuc enat |
53623 | 1604 |
|
1605 |
text {* |
|
1606 |
\noindent |
|
1607 |
This type has exactly one infinite element, @{text "ESuc (ESuc (ESuc (\<dots>)))"}, |
|
1608 |
that represents $\infty$. In addition, it has finite values of the form |
|
1609 |
@{text "ESuc (\<dots> (ESuc EZero)\<dots>)"}. |
|
53675 | 1610 |
|
1611 |
Here is an example with many constructors: |
|
52805 | 1612 |
*} |
53623 | 1613 |
|
53675 | 1614 |
codatatype 'a process = |
1615 |
Fail |
|
1616 |
| Skip (cont: "'a process") |
|
1617 |
| Action (prefix: 'a) (cont: "'a process") |
|
1618 |
| Choice (left: "'a process") (right: "'a process") |
|
1619 |
||
53750 | 1620 |
text {* |
53829 | 1621 |
\noindent |
53750 | 1622 |
Notice that the @{const cont} selector is associated with both @{const Skip} |
54146 | 1623 |
and @{const Action}. |
53750 | 1624 |
*} |
1625 |
||
53623 | 1626 |
|
1627 |
subsubsection {* Mutual Corecursion |
|
1628 |
\label{sssec:codatatype-mutual-corecursion} *} |
|
1629 |
||
1630 |
text {* |
|
1631 |
\noindent |
|
1632 |
The example below introduces a pair of \emph{mutually corecursive} types: |
|
1633 |
*} |
|
1634 |
||
1635 |
codatatype even_enat = Even_EZero | Even_ESuc odd_enat |
|
1636 |
and odd_enat = Odd_ESuc even_enat |
|
1637 |
||
1638 |
||
1639 |
subsubsection {* Nested Corecursion |
|
1640 |
\label{sssec:codatatype-nested-corecursion} *} |
|
1641 |
||
1642 |
text {* |
|
1643 |
\noindent |
|
53675 | 1644 |
The next examples feature \emph{nested corecursion}: |
53623 | 1645 |
*} |
1646 |
||
53644 | 1647 |
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 | 1648 |
|
53752 | 1649 |
text {* \blankline *} |
1650 |
||
53644 | 1651 |
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 | 1652 |
|
53752 | 1653 |
text {* \blankline *} |
1654 |
||
55350 | 1655 |
codatatype 'a sm = SM (accept: bool) (trans: "'a \<Rightarrow> 'a sm") |
53675 | 1656 |
|
52824 | 1657 |
|
53617 | 1658 |
subsection {* Command Syntax |
1659 |
\label{ssec:codatatype-command-syntax} *} |
|
52805 | 1660 |
|
53619 | 1661 |
|
53621 | 1662 |
subsubsection {* \keyw{codatatype} |
1663 |
\label{sssec:codatatype} *} |
|
53619 | 1664 |
|
52824 | 1665 |
text {* |
53829 | 1666 |
\begin{matharray}{rcl} |
1667 |
@{command_def "codatatype"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
1668 |
\end{matharray} |
|
1669 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1670 |
@{rail \<open> |
55029
61a6bf7d4b02
clarified @{rail} syntax: prefer explicit \<newline> symbol;
wenzelm
parents:
54958
diff
changeset
|
1671 |
@@{command codatatype} target? \<newline> |
55472
990651bfc65b
updated docs to reflect the new 'free_constructors' syntax
blanchet
parents:
55468
diff
changeset
|
1672 |
(@{syntax dt_name} '=' (@{syntax dt_ctor} + '|') + @'and') |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1673 |
\<close>} |
53829 | 1674 |
|
55351 | 1675 |
\medskip |
1676 |
||
53829 | 1677 |
\noindent |
52827 | 1678 |
Definitions of codatatypes have almost exactly the same syntax as for datatypes |
57094
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
1679 |
(Section~\ref{ssec:datatype-command-syntax}). The @{text "discs_sels"} option |
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
1680 |
is superfluous because discriminators and selectors are always generated for |
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
1681 |
codatatypes. |
53623 | 1682 |
*} |
1683 |
||
1684 |
||
1685 |
subsection {* Generated Constants |
|
1686 |
\label{ssec:codatatype-generated-constants} *} |
|
1687 |
||
1688 |
text {* |
|
1689 |
Given a codatatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
|
1690 |
with $m > 0$ live type variables and $n$ constructors @{text "t.C\<^sub>1"}, |
|
1691 |
\ldots, @{text "t.C\<^sub>n"}, the same auxiliary constants are generated as for |
|
1692 |
datatypes (Section~\ref{ssec:datatype-generated-constants}), except that the |
|
56655 | 1693 |
recursor is replaced by a dual concept and no size function is produced: |
53623 | 1694 |
|
55354 | 1695 |
\medskip |
1696 |
||
1697 |
\begin{tabular}{@ {}ll@ {}} |
|
1698 |
Corecursor: & |
|
56655 | 1699 |
@{text t.corec_t} |
55354 | 1700 |
\end{tabular} |
53623 | 1701 |
*} |
1702 |
||
1703 |
||
1704 |
subsection {* Generated Theorems |
|
1705 |
\label{ssec:codatatype-generated-theorems} *} |
|
1706 |
||
1707 |
text {* |
|
53829 | 1708 |
The characteristic theorems generated by @{command codatatype} are grouped in |
53623 | 1709 |
three broad categories: |
1710 |
||
1711 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1712 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1713 |
|
56655 | 1714 |
\item The \emph{free constructor theorems} |
1715 |
(Section~\ref{sssec:free-constructor-theorems}) are properties of the |
|
1716 |
constructors and destructors that can be derived for any freely generated type. |
|
1717 |
||
1718 |
\item The \emph{functorial theorems} |
|
1719 |
(Section~\ref{sssec:functorial-theorems}) are properties of datatypes related to |
|
53623 | 1720 |
their BNF nature. |
1721 |
||
56655 | 1722 |
\item The \emph{coinductive theorems} (Section~\ref{sssec:coinductive-theorems}) |
1723 |
are properties of datatypes related to their coinductive nature. |
|
53623 | 1724 |
\end{itemize} |
1725 |
||
1726 |
\noindent |
|
56655 | 1727 |
The first two categories are exactly as for datatypes. |
52824 | 1728 |
*} |
1729 |
||
53617 | 1730 |
|
53623 | 1731 |
subsubsection {* Coinductive Theorems |
1732 |
\label{sssec:coinductive-theorems} *} |
|
1733 |
||
1734 |
text {* |
|
54031 | 1735 |
The coinductive theorems are listed below for @{typ "'a llist"}: |
53623 | 1736 |
|
1737 |
\begin{indentblock} |
|
1738 |
\begin{description} |
|
1739 |
||
53643 | 1740 |
\item[\begin{tabular}{@ {}l@ {}} |
57304 | 1741 |
@{text "t."}\hthm{coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1742 |
\phantom{@{text "t."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
1743 |
D\<^sub>n, coinduct t]"}\rm: |
|
53643 | 1744 |
\end{tabular}] ~ \\ |
53623 | 1745 |
@{thm llist.coinduct[no_vars]} |
53617 | 1746 |
|
53643 | 1747 |
\item[\begin{tabular}{@ {}l@ {}} |
1748 |
@{text "t."}\hthm{strong\_coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
1749 |
\phantom{@{text "t."}\hthm{strong\_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
|
1750 |
\end{tabular}] ~ \\ |
|
1751 |
@{thm llist.strong_coinduct[no_vars]} |
|
53617 | 1752 |
|
53643 | 1753 |
\item[\begin{tabular}{@ {}l@ {}} |
57304 | 1754 |
@{text "t."}\hthm{rel_coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1755 |
\phantom{@{text "t."}\hthm{rel_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
1756 |
D\<^sub>n, coinduct pred]"}\rm: |
|
1757 |
\end{tabular}] ~ \\ |
|
1758 |
@{thm llist.rel_coinduct[no_vars]} |
|
1759 |
||
1760 |
\item[\begin{tabular}{@ {}l@ {}} |
|
53643 | 1761 |
@{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]"} \\ |
1762 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{strong\_coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
57304 | 1763 |
\phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{strong\_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: \\ |
1764 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m, case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"} \\ |
|
53643 | 1765 |
\end{tabular}] ~ \\ |
1766 |
Given $m > 1$ mutually corecursive codatatypes, these coinduction rules can be |
|
1767 |
used to prove $m$ properties simultaneously. |
|
1768 |
||
54031 | 1769 |
\item[@{text "t."}\hthm{corec}\rm:] ~ \\ |
53623 | 1770 |
@{thm llist.corec(1)[no_vars]} \\ |
1771 |
@{thm llist.corec(2)[no_vars]} |
|
1772 |
||
57490 | 1773 |
\item[@{text "t."}\hthm{corec\_code} @{text "[code]"}\rm:] ~ \\ |
1774 |
@{thm llist.corec_code[no_vars]} |
|
1775 |
||
53703 | 1776 |
\item[@{text "t."}\hthm{disc\_corec}\rm:] ~ \\ |
53643 | 1777 |
@{thm llist.disc_corec(1)[no_vars]} \\ |
1778 |
@{thm llist.disc_corec(2)[no_vars]} |
|
1779 |
||
1780 |
\item[@{text "t."}\hthm{disc\_corec\_iff} @{text "[simp]"}\rm:] ~ \\ |
|
1781 |
@{thm llist.disc_corec_iff(1)[no_vars]} \\ |
|
1782 |
@{thm llist.disc_corec_iff(2)[no_vars]} |
|
1783 |
||
1784 |
\item[@{text "t."}\hthm{sel\_corec} @{text "[simp]"}\rm:] ~ \\ |
|
1785 |
@{thm llist.sel_corec(1)[no_vars]} \\ |
|
1786 |
@{thm llist.sel_corec(2)[no_vars]} |
|
1787 |
||
53623 | 1788 |
\end{description} |
1789 |
\end{indentblock} |
|
1790 |
||
1791 |
\noindent |
|
53829 | 1792 |
For convenience, @{command codatatype} also provides the following collection: |
53623 | 1793 |
|
1794 |
\begin{indentblock} |
|
1795 |
\begin{description} |
|
1796 |
||
55896 | 1797 |
\item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.disc_corec_iff}] @{text t.sel_corec} ~ \\ |
1798 |
@{text t.map} @{text t.rel_inject} @{text t.rel_distinct} @{text t.set} |
|
53623 | 1799 |
|
1800 |
\end{description} |
|
1801 |
\end{indentblock} |
|
1802 |
*} |
|
52805 | 1803 |
|
1804 |
||
52827 | 1805 |
section {* Defining Corecursive Functions |
52805 | 1806 |
\label{sec:defining-corecursive-functions} *} |
1807 |
||
1808 |
text {* |
|
54183 | 1809 |
Corecursive functions can be specified using the @{command primcorec} and |
1810 |
\keyw{prim\-corec\-ursive} commands, which support primitive corecursion, or |
|
1811 |
using the more general \keyw{partial\_function} command. Here, the focus is on |
|
1812 |
the first two. More examples can be found in the directory |
|
55075 | 1813 |
\verb|~~/src/HOL/BNF_Examples|. |
53644 | 1814 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1815 |
Whereas recursive functions consume datatypes one constructor at a time, |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1816 |
corecursive functions construct codatatypes one constructor at a time. |
53752 | 1817 |
Partly reflecting a lack of agreement among proponents of coalgebraic methods, |
1818 |
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
|
1819 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1820 |
\begin{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1821 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1822 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1823 |
\abovedisplayskip=.5\abovedisplayskip |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1824 |
\belowdisplayskip=.5\belowdisplayskip |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1825 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1826 |
\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
|
1827 |
\[@{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
|
1828 |
equations of the form |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1829 |
\[@{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
|
1830 |
This style is popular in the coalgebraic literature. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1831 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1832 |
\item The \emph{constructor view} specifies $f$ by equations of the form |
54183 | 1833 |
\[@{text "\<dots> \<Longrightarrow> f x\<^sub>1 \<dots> x\<^sub>n = C\<^sub>j \<dots>"}\] |
53752 | 1834 |
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
|
1835 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1836 |
\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
|
1837 |
\[@{text "f x\<^sub>1 \<dots> x\<^sub>n = \<dots>"}\] |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1838 |
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
|
1839 |
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
|
1840 |
style. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1841 |
\end{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1842 |
|
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
|
1843 |
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
|
1844 |
characteristic theorems for all three styles are generated. |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1845 |
|
52828 | 1846 |
%%% TODO: partial_function? E.g. for defining tail recursive function on lazy |
1847 |
%%% lists (cf. terminal0 in TLList.thy) |
|
52805 | 1848 |
*} |
1849 |
||
52824 | 1850 |
|
53617 | 1851 |
subsection {* Introductory Examples |
1852 |
\label{ssec:primcorec-introductory-examples} *} |
|
52805 | 1853 |
|
53646 | 1854 |
text {* |
1855 |
Primitive corecursion is illustrated through concrete examples based on the |
|
1856 |
codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More |
|
55075 | 1857 |
examples can be found in the directory \verb|~~/src/HOL/BNF_Examples|. The code |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1858 |
view is favored in the examples below. Sections |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1859 |
\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
|
1860 |
present the same examples expressed using the constructor and destructor views. |
53646 | 1861 |
*} |
1862 |
||
53644 | 1863 |
subsubsection {* Simple Corecursion |
1864 |
\label{sssec:primcorec-simple-corecursion} *} |
|
1865 |
||
53646 | 1866 |
text {* |
53752 | 1867 |
Following the code view, corecursive calls are allowed on the right-hand side as |
1868 |
long as they occur under a constructor, which itself appears either directly to |
|
1869 |
the right of the equal sign or in a conditional expression: |
|
53646 | 1870 |
*} |
1871 |
||
53826 | 1872 |
primcorec literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
54072 | 1873 |
"literate g x = LCons x (literate g (g x))" |
53647 | 1874 |
|
53677 | 1875 |
text {* \blankline *} |
1876 |
||
53826 | 1877 |
primcorec siterate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a stream" where |
54072 | 1878 |
"siterate g x = SCons x (siterate g (g x))" |
53644 | 1879 |
|
53646 | 1880 |
text {* |
1881 |
\noindent |
|
1882 |
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
|
1883 |
\emph{productive}. The above functions compute the infinite lazy list or stream |
54072 | 1884 |
@{text "[x, g x, g (g x), \<dots>]"}. Productivity guarantees that prefixes |
1885 |
@{text "[x, g x, g (g x), \<dots>, (g ^^ k) x]"} of arbitrary finite length |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1886 |
@{text k} can be computed by unfolding the code equation a finite number of |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
1887 |
times. |
53646 | 1888 |
|
53752 | 1889 |
Corecursive functions construct codatatype values, but nothing prevents them |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
1890 |
from also consuming such values. The following function drops every second |
53675 | 1891 |
element in a stream: |
1892 |
*} |
|
1893 |
||
53826 | 1894 |
primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
53675 | 1895 |
"every_snd s = SCons (shd s) (stl (stl s))" |
1896 |
||
1897 |
text {* |
|
53752 | 1898 |
\noindent |
56124 | 1899 |
Constructs such as @{text "let"}--@{text "in"}, @{text |
1900 |
"if"}--@{text "then"}--@{text "else"}, and @{text "case"}--@{text "of"} may |
|
53646 | 1901 |
appear around constructors that guard corecursive calls: |
1902 |
*} |
|
1903 |
||
54072 | 1904 |
primcorec lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53644 | 1905 |
"lappend xs ys = |
1906 |
(case xs of |
|
1907 |
LNil \<Rightarrow> ys |
|
1908 |
| LCons x xs' \<Rightarrow> LCons x (lappend xs' ys))" |
|
1909 |
||
53646 | 1910 |
text {* |
53752 | 1911 |
\noindent |
54402 | 1912 |
Pattern matching is not supported by @{command primcorec}. Fortunately, it is |
1913 |
easy to generate pattern-maching equations using the \keyw{simps\_of\_case} |
|
1914 |
command provided by the theory \verb|~~/src/HOL/Library/Simps_Case_Conv|. |
|
1915 |
*} |
|
1916 |
||
1917 |
simps_of_case lappend_simps: lappend.code |
|
1918 |
||
1919 |
text {* |
|
1920 |
This generates the lemma collection @{thm [source] lappend_simps}: |
|
1921 |
% |
|
55355 | 1922 |
\begin{gather*% |
1923 |
} |
|
1924 |
@{thm lappend_simps(1)[no_vars]} \\ |
|
1925 |
@{thm lappend_simps(2)[no_vars]} |
|
1926 |
\end{gather*% |
|
1927 |
} |
|
54402 | 1928 |
% |
53646 | 1929 |
Corecursion is useful to specify not only functions but also infinite objects: |
1930 |
*} |
|
1931 |
||
53826 | 1932 |
primcorec infty :: enat where |
53644 | 1933 |
"infty = ESuc infty" |
1934 |
||
53646 | 1935 |
text {* |
53752 | 1936 |
\noindent |
1937 |
The example below constructs a pseudorandom process value. It takes a stream of |
|
53675 | 1938 |
actions (@{text s}), a pseudorandom function generator (@{text f}), and a |
1939 |
pseudorandom seed (@{text n}): |
|
1940 |
*} |
|
1941 |
||
54072 | 1942 |
primcorec |
53752 | 1943 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
1944 |
where |
|
53675 | 1945 |
"random_process s f n = |
1946 |
(if n mod 4 = 0 then |
|
1947 |
Fail |
|
1948 |
else if n mod 4 = 1 then |
|
1949 |
Skip (random_process s f (f n)) |
|
1950 |
else if n mod 4 = 2 then |
|
1951 |
Action (shd s) (random_process (stl s) f (f n)) |
|
1952 |
else |
|
1953 |
Choice (random_process (every_snd s) (f \<circ> f) (f n)) |
|
1954 |
(random_process (every_snd (stl s)) (f \<circ> f) (f (f n))))" |
|
1955 |
||
1956 |
text {* |
|
1957 |
\noindent |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1958 |
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
|
1959 |
sequentially. This is visible in the generated theorems. The constructor and |
53752 | 1960 |
destructor views offer nonsequential alternatives. |
53675 | 1961 |
*} |
1962 |
||
53644 | 1963 |
|
1964 |
subsubsection {* Mutual Corecursion |
|
1965 |
\label{sssec:primcorec-mutual-corecursion} *} |
|
1966 |
||
53647 | 1967 |
text {* |
1968 |
The syntax for mutually corecursive functions over mutually corecursive |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1969 |
datatypes is unsurprising: |
53647 | 1970 |
*} |
1971 |
||
53826 | 1972 |
primcorec |
53644 | 1973 |
even_infty :: even_enat and |
1974 |
odd_infty :: odd_enat |
|
1975 |
where |
|
1976 |
"even_infty = Even_ESuc odd_infty" | |
|
1977 |
"odd_infty = Odd_ESuc even_infty" |
|
1978 |
||
1979 |
||
1980 |
subsubsection {* Nested Corecursion |
|
1981 |
\label{sssec:primcorec-nested-corecursion} *} |
|
1982 |
||
53647 | 1983 |
text {* |
1984 |
The next pair of examples generalize the @{const literate} and @{const siterate} |
|
1985 |
functions (Section~\ref{sssec:primcorec-nested-corecursion}) to possibly |
|
1986 |
infinite trees in which subnodes are organized either as a lazy list (@{text |
|
54072 | 1987 |
tree\<^sub>i\<^sub>i}) or as a finite set (@{text tree\<^sub>i\<^sub>s}). They rely on the map functions of |
1988 |
the nesting type constructors to lift the corecursive calls: |
|
53647 | 1989 |
*} |
1990 |
||
53826 | 1991 |
primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
54072 | 1992 |
"iterate\<^sub>i\<^sub>i g x = Node\<^sub>i\<^sub>i x (lmap (iterate\<^sub>i\<^sub>i g) (g x))" |
53644 | 1993 |
|
53677 | 1994 |
text {* \blankline *} |
1995 |
||
53826 | 1996 |
primcorec iterate\<^sub>i\<^sub>s :: "('a \<Rightarrow> 'a fset) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>s" where |
54072 | 1997 |
"iterate\<^sub>i\<^sub>s g x = Node\<^sub>i\<^sub>s x (fimage (iterate\<^sub>i\<^sub>s g) (g x))" |
53644 | 1998 |
|
52805 | 1999 |
text {* |
53752 | 2000 |
\noindent |
54072 | 2001 |
Both examples follow the usual format for constructor arguments associated |
2002 |
with nested recursive occurrences of the datatype. Consider |
|
2003 |
@{const iterate\<^sub>i\<^sub>i}. The term @{term "g x"} constructs an @{typ "'a llist"} |
|
2004 |
value, which is turned into an @{typ "'a tree\<^sub>i\<^sub>i llist"} value using |
|
2005 |
@{const lmap}. |
|
2006 |
||
2007 |
This format may sometimes feel artificial. The following function constructs |
|
2008 |
a tree with a single, infinite branch from a stream: |
|
2009 |
*} |
|
2010 |
||
2011 |
primcorec tree\<^sub>i\<^sub>i_of_stream :: "'a stream \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
|
2012 |
"tree\<^sub>i\<^sub>i_of_stream s = |
|
2013 |
Node\<^sub>i\<^sub>i (shd s) (lmap tree\<^sub>i\<^sub>i_of_stream (LCons (stl s) LNil))" |
|
2014 |
||
2015 |
text {* |
|
2016 |
\noindent |
|
54955
cf8d429dc24e
reintroduce recursive calls under constructors, taken out in 8dd0e0316881 mainly and in subsequent changes
blanchet
parents:
54832
diff
changeset
|
2017 |
A more natural syntax, also supported by Isabelle, is to move corecursive calls |
cf8d429dc24e
reintroduce recursive calls under constructors, taken out in 8dd0e0316881 mainly and in subsequent changes
blanchet
parents:
54832
diff
changeset
|
2018 |
under constructors: |
54072 | 2019 |
*} |
2020 |
||
54955
cf8d429dc24e
reintroduce recursive calls under constructors, taken out in 8dd0e0316881 mainly and in subsequent changes
blanchet
parents:
54832
diff
changeset
|
2021 |
primcorec (*<*)(in late) (*>*)tree\<^sub>i\<^sub>i_of_stream :: "'a stream \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
55350 | 2022 |
"tree\<^sub>i\<^sub>i_of_stream s = |
2023 |
Node\<^sub>i\<^sub>i (shd s) (LCons (tree\<^sub>i\<^sub>i_of_stream (stl s)) LNil)" |
|
54072 | 2024 |
|
2025 |
text {* |
|
2026 |
The next example illustrates corecursion through functions, which is a bit |
|
2027 |
special. Deterministic finite automata (DFAs) are traditionally defined as |
|
2028 |
5-tuples @{text "(Q, \<Sigma>, \<delta>, q\<^sub>0, F)"}, where @{text Q} is a finite set of states, |
|
53675 | 2029 |
@{text \<Sigma>} is a finite alphabet, @{text \<delta>} is a transition function, @{text q\<^sub>0} |
2030 |
is an initial state, and @{text F} is a set of final states. The following |
|
55350 | 2031 |
function translates a DFA into a state machine: |
53675 | 2032 |
*} |
2033 |
||
55350 | 2034 |
primcorec (*<*)(in early) (*>*)sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2035 |
"sm_of_dfa \<delta> F q = SM (q \<in> F) (sm_of_dfa \<delta> F \<circ> \<delta> q)" |
|
53675 | 2036 |
|
53751 | 2037 |
text {* |
2038 |
\noindent |
|
2039 |
The map function for the function type (@{text \<Rightarrow>}) is composition |
|
54181 | 2040 |
(@{text "op \<circ>"}). For convenience, corecursion through functions can |
54182 | 2041 |
also be expressed using $\lambda$-abstractions and function application rather |
54031 | 2042 |
than through composition. For example: |
53751 | 2043 |
*} |
2044 |
||
55350 | 2045 |
primcorec sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2046 |
"sm_of_dfa \<delta> F q = SM (q \<in> F) (\<lambda>a. sm_of_dfa \<delta> F (\<delta> q a))" |
|
53752 | 2047 |
|
2048 |
text {* \blankline *} |
|
2049 |
||
55350 | 2050 |
primcorec empty_sm :: "'a sm" where |
2051 |
"empty_sm = SM False (\<lambda>_. empty_sm)" |
|
53751 | 2052 |
|
53752 | 2053 |
text {* \blankline *} |
2054 |
||
55350 | 2055 |
primcorec not_sm :: "'a sm \<Rightarrow> 'a sm" where |
2056 |
"not_sm M = SM (\<not> accept M) (\<lambda>a. not_sm (trans M a))" |
|
53751 | 2057 |
|
53752 | 2058 |
text {* \blankline *} |
2059 |
||
55350 | 2060 |
primcorec or_sm :: "'a sm \<Rightarrow> 'a sm \<Rightarrow> 'a sm" where |
2061 |
"or_sm M N = |
|
2062 |
SM (accept M \<or> accept N) (\<lambda>a. or_sm (trans M a) (trans N a))" |
|
53751 | 2063 |
|
54182 | 2064 |
text {* |
2065 |
\noindent |
|
2066 |
For recursion through curried $n$-ary functions, $n$ applications of |
|
2067 |
@{term "op \<circ>"} are necessary. The examples below illustrate the case where |
|
2068 |
$n = 2$: |
|
2069 |
*} |
|
2070 |
||
55350 | 2071 |
codatatype ('a, 'b) sm2 = |
2072 |
SM2 (accept2: bool) (trans2: "'a \<Rightarrow> 'b \<Rightarrow> ('a, 'b) sm2") |
|
54182 | 2073 |
|
2074 |
text {* \blankline *} |
|
2075 |
||
2076 |
primcorec |
|
55350 | 2077 |
(*<*)(in early) (*>*)sm2_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> ('a, 'b) sm2" |
54182 | 2078 |
where |
55350 | 2079 |
"sm2_of_dfa \<delta> F q = SM2 (q \<in> F) (op \<circ> (op \<circ> (sm2_of_dfa \<delta> F)) (\<delta> q))" |
54182 | 2080 |
|
2081 |
text {* \blankline *} |
|
2082 |
||
2083 |
primcorec |
|
55350 | 2084 |
sm2_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> ('a, 'b) sm2" |
54182 | 2085 |
where |
55350 | 2086 |
"sm2_of_dfa \<delta> F q = SM2 (q \<in> F) (\<lambda>a b. sm2_of_dfa \<delta> F (\<delta> q a b))" |
54182 | 2087 |
|
53644 | 2088 |
|
2089 |
subsubsection {* Nested-as-Mutual Corecursion |
|
2090 |
\label{sssec:primcorec-nested-as-mutual-corecursion} *} |
|
2091 |
||
53647 | 2092 |
text {* |
2093 |
Just as it is possible to recurse over nested recursive datatypes as if they |
|
2094 |
were mutually recursive |
|
2095 |
(Section~\ref{sssec:primrec-nested-as-mutual-recursion}), it is possible to |
|
53752 | 2096 |
pretend that nested codatatypes are mutually corecursive. For example: |
53647 | 2097 |
*} |
2098 |
||
54287 | 2099 |
(*<*) |
2100 |
context late |
|
2101 |
begin |
|
2102 |
(*>*) |
|
54072 | 2103 |
primcorec |
54287 | 2104 |
iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" and |
53644 | 2105 |
iterates\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a llist \<Rightarrow> 'a tree\<^sub>i\<^sub>i llist" |
2106 |
where |
|
54072 | 2107 |
"iterate\<^sub>i\<^sub>i g x = Node\<^sub>i\<^sub>i x (iterates\<^sub>i\<^sub>i g (g x))" | |
2108 |
"iterates\<^sub>i\<^sub>i g xs = |
|
53644 | 2109 |
(case xs of |
2110 |
LNil \<Rightarrow> LNil |
|
54072 | 2111 |
| LCons x xs' \<Rightarrow> LCons (iterate\<^sub>i\<^sub>i g x) (iterates\<^sub>i\<^sub>i g xs'))" |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2112 |
|
54287 | 2113 |
text {* |
2114 |
\noindent |
|
2115 |
Coinduction rules are generated as |
|
2116 |
@{thm [source] iterate\<^sub>i\<^sub>i.coinduct}, |
|
2117 |
@{thm [source] iterates\<^sub>i\<^sub>i.coinduct}, and |
|
2118 |
@{thm [source] iterate\<^sub>i\<^sub>i_iterates\<^sub>i\<^sub>i.coinduct} |
|
2119 |
and analogously for @{text strong_coinduct}. These rules and the |
|
2120 |
underlying corecursors are generated on a per-need basis and are kept in a cache |
|
2121 |
to speed up subsequent definitions. |
|
2122 |
*} |
|
2123 |
||
2124 |
(*<*) |
|
2125 |
end |
|
2126 |
(*>*) |
|
2127 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2128 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2129 |
subsubsection {* Constructor View |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2130 |
\label{ssec:primrec-constructor-view} *} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2131 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2132 |
(*<*) |
54182 | 2133 |
locale ctr_view |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2134 |
begin |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2135 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2136 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2137 |
text {* |
53750 | 2138 |
The constructor view is similar to the code view, but there is one separate |
2139 |
conditional equation per constructor rather than a single unconditional |
|
2140 |
equation. Examples that rely on a single constructor, such as @{const literate} |
|
2141 |
and @{const siterate}, are identical in both styles. |
|
2142 |
||
2143 |
Here is an example where there is a difference: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2144 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2145 |
|
53826 | 2146 |
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
|
2147 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lappend xs ys = LNil" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2148 |
"_ \<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
|
2149 |
(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
|
2150 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2151 |
text {* |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2152 |
\noindent |
53752 | 2153 |
With the constructor view, we must distinguish between the @{const LNil} and |
2154 |
the @{const LCons} case. The condition for @{const LCons} is |
|
2155 |
left implicit, as the negation of that for @{const LNil}. |
|
53750 | 2156 |
|
2157 |
For this example, the constructor view is slighlty more involved than the |
|
2158 |
code equation. Recall the code view version presented in |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2159 |
Section~\ref{sssec:primcorec-simple-corecursion}. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2160 |
% TODO: \[{thm code_view.lappend.code}\] |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2161 |
The constructor view requires us to analyze the second argument (@{term ys}). |
53752 | 2162 |
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
|
2163 |
% TODO: \[{thm lappend.code}\] |
53750 | 2164 |
|
53752 | 2165 |
In contrast, the next example is arguably more naturally expressed in the |
2166 |
constructor view: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2167 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2168 |
|
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2169 |
primcorec |
53752 | 2170 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
2171 |
where |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2172 |
"n mod 4 = 0 \<Longrightarrow> random_process s f n = Fail" | |
53752 | 2173 |
"n mod 4 = 1 \<Longrightarrow> |
2174 |
random_process s f n = Skip (random_process s f (f n))" | |
|
2175 |
"n mod 4 = 2 \<Longrightarrow> |
|
2176 |
random_process s f n = Action (shd s) (random_process (stl s) f (f n))" | |
|
2177 |
"n mod 4 = 3 \<Longrightarrow> |
|
2178 |
random_process s f n = Choice (random_process (every_snd s) f (f n)) |
|
53826 | 2179 |
(random_process (every_snd (stl s)) f (f n))" |
2180 |
(*<*) |
|
53644 | 2181 |
end |
2182 |
(*>*) |
|
52805 | 2183 |
|
53750 | 2184 |
text {* |
53752 | 2185 |
\noindent |
53750 | 2186 |
Since there is no sequentiality, we can apply the equation for @{const Choice} |
53752 | 2187 |
without having first to discharge @{term "n mod (4\<Colon>int) \<noteq> 0"}, |
2188 |
@{term "n mod (4\<Colon>int) \<noteq> 1"}, and |
|
2189 |
@{term "n mod (4\<Colon>int) \<noteq> 2"}. |
|
53750 | 2190 |
The price to pay for this elegance is that we must discharge exclusivity proof |
2191 |
obligations, one for each pair of conditions |
|
53752 | 2192 |
@{term "(n mod (4\<Colon>int) = i, n mod (4\<Colon>int) = j)"} |
2193 |
with @{term "i < j"}. If we prefer not to discharge any obligations, we can |
|
2194 |
enable the @{text "sequential"} option. This pushes the problem to the users of |
|
2195 |
the generated properties. |
|
53750 | 2196 |
%Here are more examples to conclude: |
2197 |
*} |
|
2198 |
||
52824 | 2199 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2200 |
subsubsection {* Destructor View |
53752 | 2201 |
\label{ssec:primrec-destructor-view} *} |
2202 |
||
2203 |
(*<*) |
|
54182 | 2204 |
locale dtr_view |
53752 | 2205 |
begin |
2206 |
(*>*) |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2207 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2208 |
text {* |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2209 |
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
|
2210 |
determine which constructor to choose, and these conditions are interpreted |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2211 |
sequentially or not depending on the @{text "sequential"} option. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2212 |
Consider the following examples: |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2213 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2214 |
|
53826 | 2215 |
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
|
2216 |
"\<not> lnull (literate _ x)" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2217 |
"lhd (literate _ x) = x" | |
54072 | 2218 |
"ltl (literate g x) = literate g (g x)" |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2219 |
|
53752 | 2220 |
text {* \blankline *} |
2221 |
||
53826 | 2222 |
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
|
2223 |
"shd (siterate _ x) = x" | |
54072 | 2224 |
"stl (siterate g x) = siterate g (g x)" |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2225 |
|
53752 | 2226 |
text {* \blankline *} |
2227 |
||
53826 | 2228 |
primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2229 |
"shd (every_snd s) = shd s" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2230 |
"stl (every_snd s) = stl (stl s)" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2231 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2232 |
text {* |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2233 |
\noindent |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2234 |
The first formula in the @{const literate} specification indicates which |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2235 |
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
|
2236 |
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
|
2237 |
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
|
2238 |
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
|
2239 |
Their arguments are unrestricted. |
53750 | 2240 |
|
2241 |
The next example shows how to specify functions that rely on more than one |
|
2242 |
constructor: |
|
2243 |
*} |
|
2244 |
||
53826 | 2245 |
primcorec lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53750 | 2246 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lnull (lappend xs ys)" | |
2247 |
"lhd (lappend xs ys) = lhd (if lnull xs then ys else xs)" | |
|
2248 |
"ltl (lappend xs ys) = (if xs = LNil then ltl ys else lappend (ltl xs) ys)" |
|
2249 |
||
2250 |
text {* |
|
2251 |
\noindent |
|
2252 |
For a codatatype with $n$ constructors, it is sufficient to specify $n - 1$ |
|
2253 |
discriminator formulas. The command will then assume that the remaining |
|
2254 |
constructor should be taken otherwise. This can be made explicit by adding |
|
2255 |
*} |
|
2256 |
||
2257 |
(*<*) |
|
2258 |
end |
|
2259 |
||
54182 | 2260 |
locale dtr_view2 |
2261 |
begin |
|
2262 |
||
53826 | 2263 |
primcorec lappend :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
53750 | 2264 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lnull (lappend xs ys)" | |
55350 | 2265 |
"lhd (lappend xs ys) = lhd (if lnull xs then ys else xs)" | |
2266 |
"ltl (lappend xs ys) = (if xs = LNil then ltl ys else lappend (ltl xs) ys)" | |
|
53750 | 2267 |
(*>*) |
53752 | 2268 |
"_ \<Longrightarrow> \<not> lnull (lappend xs ys)" |
53750 | 2269 |
|
2270 |
text {* |
|
2271 |
\noindent |
|
53752 | 2272 |
to the specification. The generated selector theorems are conditional. |
2273 |
||
2274 |
The next example illustrates how to cope with selectors defined for several |
|
53750 | 2275 |
constructors: |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2276 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2277 |
|
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2278 |
primcorec |
53752 | 2279 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
2280 |
where |
|
57091 | 2281 |
"n mod 4 = 0 \<Longrightarrow> random_process s f n = Fail" | |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2282 |
"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
|
2283 |
"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
|
2284 |
"n mod 4 = 3 \<Longrightarrow> is_Choice (random_process s f n)" | |
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2285 |
"cont (random_process s f n) = random_process s f (f n)" of Skip | |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2286 |
"prefix (random_process s f n) = shd s" | |
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2287 |
"cont (random_process s f n) = random_process (stl s) f (f n)" of Action | |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2288 |
"left (random_process s f n) = random_process (every_snd s) f (f n)" | |
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2289 |
"right (random_process s f n) = random_process (every_snd (stl s)) f (f n)" |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2290 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2291 |
text {* |
53750 | 2292 |
\noindent |
2293 |
Using the @{text "of"} keyword, different equations are specified for @{const |
|
2294 |
cont} depending on which constructor is selected. |
|
2295 |
||
2296 |
Here are more examples to conclude: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2297 |
*} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2298 |
|
53826 | 2299 |
primcorec |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2300 |
even_infty :: even_enat and |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2301 |
odd_infty :: odd_enat |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2302 |
where |
57091 | 2303 |
"even_infty \<noteq> Even_EZero" | |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2304 |
"un_Even_ESuc even_infty = odd_infty" | |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2305 |
"un_Odd_ESuc odd_infty = even_infty" |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2306 |
|
53752 | 2307 |
text {* \blankline *} |
2308 |
||
53826 | 2309 |
primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
54072 | 2310 |
"lbl\<^sub>i\<^sub>i (iterate\<^sub>i\<^sub>i g x) = x" | |
2311 |
"sub\<^sub>i\<^sub>i (iterate\<^sub>i\<^sub>i g x) = lmap (iterate\<^sub>i\<^sub>i g) (g x)" |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2312 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2313 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2314 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2315 |
|
53750 | 2316 |
|
53617 | 2317 |
subsection {* Command Syntax |
2318 |
\label{ssec:primcorec-command-syntax} *} |
|
2319 |
||
2320 |
||
53826 | 2321 |
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
|
2322 |
\label{sssec:primcorecursive-and-primcorec} *} |
52840 | 2323 |
|
2324 |
text {* |
|
53829 | 2325 |
\begin{matharray}{rcl} |
2326 |
@{command_def "primcorec"} & : & @{text "local_theory \<rightarrow> local_theory"} \\ |
|
2327 |
@{command_def "primcorecursive"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2328 |
\end{matharray} |
|
52840 | 2329 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2330 |
@{rail \<open> |
55029
61a6bf7d4b02
clarified @{rail} syntax: prefer explicit \<newline> symbol;
wenzelm
parents:
54958
diff
changeset
|
2331 |
(@@{command primcorec} | @@{command primcorecursive}) target? \<newline> |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2332 |
@{syntax pcr_option}? fixes @'where' (@{syntax pcr_formula} + '|') |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2333 |
; |
53828 | 2334 |
@{syntax_def pcr_option}: '(' ('sequential' | 'exhaustive') ')' |
52840 | 2335 |
; |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2336 |
@{syntax_def pcr_formula}: thmdecl? prop (@'of' (term * ))? |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2337 |
\<close>} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2338 |
|
55351 | 2339 |
\medskip |
2340 |
||
2341 |
\noindent |
|
55474 | 2342 |
The @{command primcorec} and @{command primcorecursive} commands introduce a set |
2343 |
of mutually corecursive functions over codatatypes. |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2344 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2345 |
The syntactic entity \synt{target} can be used to specify a local context, |
55474 | 2346 |
\synt{fixes} denotes a list of names with optional type signatures, |
2347 |
\synt{thmdecl} denotes an optional name for the formula that follows, and |
|
2348 |
\synt{prop} denotes a HOL proposition \cite{isabelle-isar-ref}. |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2349 |
|
56124 | 2350 |
The optional target is optionally followed by one or both of the following |
2351 |
options: |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2352 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2353 |
\begin{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2354 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2355 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2356 |
\item |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2357 |
The @{text "sequential"} option indicates that the conditions in specifications |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2358 |
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
|
2359 |
sequentially. |
53826 | 2360 |
|
2361 |
\item |
|
2362 |
The @{text "exhaustive"} option indicates that the conditions in specifications |
|
2363 |
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
|
2364 |
\end{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2365 |
|
55474 | 2366 |
The @{command primcorec} command is an abbreviation for @{command |
2367 |
primcorecursive} with @{text "by auto?"} to discharge any emerging proof |
|
2368 |
obligations. |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2369 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2370 |
%%% TODO: elaborate on format of the propositions |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2371 |
%%% TODO: elaborate on mutual and nested-to-mutual |
52840 | 2372 |
*} |
52794 | 2373 |
|
52824 | 2374 |
|
53619 | 2375 |
(* |
52840 | 2376 |
subsection {* Generated Theorems |
2377 |
\label{ssec:primcorec-generated-theorems} *} |
|
53619 | 2378 |
*) |
52794 | 2379 |
|
2380 |
||
53623 | 2381 |
(* |
2382 |
subsection {* Recursive Default Values for Selectors |
|
2383 |
\label{ssec:primcorec-recursive-default-values-for-selectors} *} |
|
2384 |
||
2385 |
text {* |
|
2386 |
partial_function to the rescue |
|
2387 |
*} |
|
2388 |
*) |
|
2389 |
||
2390 |
||
55351 | 2391 |
section {* Introducing Bounded Natural Functors |
2392 |
\label{sec:introducing-bounded-natural-functors} *} |
|
52792 | 2393 |
|
52805 | 2394 |
text {* |
53647 | 2395 |
The (co)datatype package can be set up to allow nested recursion through |
55350 | 2396 |
arbitrary type constructors, as long as they adhere to the BNF requirements |
2397 |
and are registered as BNFs. It is also possible to declare a BNF abstractly |
|
2398 |
without specifying its internal structure. |
|
52805 | 2399 |
*} |
2400 |
||
52824 | 2401 |
|
55350 | 2402 |
subsection {* Bounded Natural Functors |
2403 |
\label{ssec:bounded-natural-functors} *} |
|
2404 |
||
2405 |
text {* |
|
2406 |
Bounded natural functors (BNFs) are a semantic criterion for where |
|
2407 |
(co)re\-cur\-sion may appear on the right-hand side of an equation |
|
2408 |
\cite{traytel-et-al-2012,blanchette-et-al-wit}. |
|
2409 |
||
2410 |
An $n$-ary BNF is a type constructor equipped with a map function |
|
2411 |
(functorial action), $n$ set functions (natural transformations), |
|
2412 |
and an infinite cardinal bound that satisfy certain properties. |
|
2413 |
For example, @{typ "'a llist"} is a unary BNF. |
|
2414 |
Its relator @{text "llist_all2 \<Colon> |
|
2415 |
('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> |
|
2416 |
'a llist \<Rightarrow> 'b llist \<Rightarrow> bool"} |
|
2417 |
extends binary predicates over elements to binary predicates over parallel |
|
2418 |
lazy lists. The cardinal bound limits the number of elements returned by the |
|
2419 |
set function; it may not depend on the cardinality of @{typ 'a}. |
|
2420 |
||
2421 |
The type constructors introduced by @{command datatype_new} and |
|
2422 |
@{command codatatype} are automatically registered as BNFs. In addition, a |
|
2423 |
number of old-style datatypes and non-free types are preregistered. |
|
2424 |
||
2425 |
Given an $n$-ary BNF, the $n$ type variables associated with set functions, |
|
2426 |
and on which the map function acts, are \emph{live}; any other variables are |
|
2427 |
\emph{dead}. Nested (co)recursion can only take place through live variables. |
|
2428 |
*} |
|
2429 |
||
2430 |
||
2431 |
subsection {* Introductory Examples |
|
2432 |
\label{ssec:bnf-introductory-examples} *} |
|
52805 | 2433 |
|
2434 |
text {* |
|
55350 | 2435 |
The example below shows how to register a type as a BNF using the @{command bnf} |
2436 |
command. Some of the proof obligations are best viewed with the theory |
|
2437 |
@{theory Cardinal_Notations}, located in \verb|~~/src/HOL/Library|, |
|
2438 |
imported. |
|
2439 |
||
2440 |
The type is simply a copy of the function space @{typ "'d \<Rightarrow> 'a"}, where @{typ 'a} |
|
2441 |
is live and @{typ 'd} is dead. We introduce it together with its map function, |
|
2442 |
set function, and relator. |
|
52805 | 2443 |
*} |
55350 | 2444 |
|
2445 |
typedef ('d, 'a) fn = "UNIV \<Colon> ('d \<Rightarrow> 'a) set" |
|
2446 |
by simp |
|
2447 |
||
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2448 |
text {* \blankline *} |
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2449 |
|
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2450 |
setup_lifting type_definition_fn |
55350 | 2451 |
|
2452 |
text {* \blankline *} |
|
2453 |
||
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2454 |
lift_definition map_fn :: "('a \<Rightarrow> 'b) \<Rightarrow> ('d, 'a) fn \<Rightarrow> ('d, 'b) fn" is "op \<circ>" . |
55350 | 2455 |
|
2456 |
text {* \blankline *} |
|
2457 |
||
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2458 |
lift_definition set_fn :: "('d, 'a) fn \<Rightarrow> 'a set" is range . |
55350 | 2459 |
|
2460 |
text {* \blankline *} |
|
2461 |
||
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2462 |
lift_definition |
55350 | 2463 |
rel_fn :: "('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> ('d, 'a) fn \<Rightarrow> ('d, 'b) fn \<Rightarrow> bool" |
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2464 |
is |
55945 | 2465 |
"rel_fun (op =)" . |
55350 | 2466 |
|
2467 |
text {* \blankline *} |
|
2468 |
||
2469 |
bnf "('d, 'a) fn" |
|
2470 |
map: map_fn |
|
2471 |
sets: set_fn |
|
2472 |
bd: "natLeq +c |UNIV :: 'd set|" |
|
2473 |
rel: rel_fn |
|
2474 |
proof - |
|
2475 |
show "map_fn id = id" |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2476 |
by transfer auto |
55350 | 2477 |
next |
2478 |
fix F G show "map_fn (G \<circ> F) = map_fn G \<circ> map_fn F" |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2479 |
by transfer (auto simp add: comp_def) |
55350 | 2480 |
next |
2481 |
fix F f g |
|
2482 |
assume "\<And>x. x \<in> set_fn F \<Longrightarrow> f x = g x" |
|
2483 |
thus "map_fn f F = map_fn g F" |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2484 |
by transfer auto |
55350 | 2485 |
next |
2486 |
fix f show "set_fn \<circ> map_fn f = op ` f \<circ> set_fn" |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2487 |
by transfer (auto simp add: comp_def) |
55350 | 2488 |
next |
2489 |
show "card_order (natLeq +c |UNIV \<Colon> 'd set| )" |
|
2490 |
apply (rule card_order_csum) |
|
2491 |
apply (rule natLeq_card_order) |
|
2492 |
by (rule card_of_card_order_on) |
|
2493 |
next |
|
2494 |
show "cinfinite (natLeq +c |UNIV \<Colon> 'd set| )" |
|
2495 |
apply (rule cinfinite_csum) |
|
2496 |
apply (rule disjI1) |
|
2497 |
by (rule natLeq_cinfinite) |
|
2498 |
next |
|
2499 |
fix F :: "('d, 'a) fn" |
|
2500 |
have "|set_fn F| \<le>o |UNIV \<Colon> 'd set|" (is "_ \<le>o ?U") |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2501 |
by transfer (rule card_of_image) |
55350 | 2502 |
also have "?U \<le>o natLeq +c ?U" |
2503 |
by (rule ordLeq_csum2) (rule card_of_Card_order) |
|
2504 |
finally show "|set_fn F| \<le>o natLeq +c |UNIV \<Colon> 'd set|" . |
|
2505 |
next |
|
2506 |
fix R S |
|
2507 |
show "rel_fn R OO rel_fn S \<le> rel_fn (R OO S)" |
|
55945 | 2508 |
by (rule, transfer) (auto simp add: rel_fun_def) |
55350 | 2509 |
next |
2510 |
fix R |
|
2511 |
show "rel_fn R = |
|
57398 | 2512 |
(BNF_Def.Grp {x. set_fn x \<subseteq> Collect (split R)} (map_fn fst))\<inverse>\<inverse> OO |
2513 |
BNF_Def.Grp {x. set_fn x \<subseteq> Collect (split R)} (map_fn snd)" |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2514 |
unfolding Grp_def fun_eq_iff relcompp.simps conversep.simps |
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2515 |
apply transfer |
55945 | 2516 |
unfolding rel_fun_def subset_iff image_iff |
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2517 |
by auto (force, metis pair_collapse) |
55350 | 2518 |
qed |
2519 |
||
2520 |
text {* \blankline *} |
|
2521 |
||
2522 |
print_theorems |
|
2523 |
print_bnfs |
|
2524 |
||
2525 |
text {* |
|
2526 |
\noindent |
|
2527 |
Using \keyw{print\_theorems} and @{keyword print_bnfs}, we can contemplate and |
|
2528 |
show the world what we have achieved. |
|
2529 |
||
2530 |
This particular example does not need any nonemptiness witness, because the |
|
2531 |
one generated by default is good enough, but in general this would be |
|
2532 |
necessary. See \verb|~~/src/HOL/Basic_BNFs.thy|, |
|
2533 |
\verb|~~/src/HOL/Library/FSet.thy|, and \verb|~~/src/HOL/Library/Multiset.thy| |
|
2534 |
for further examples of BNF registration, some of which feature custom |
|
2535 |
witnesses. |
|
2536 |
||
56942 | 2537 |
The next example declares a BNF axiomatically. The @{command bnf_axiomatization} command |
55350 | 2538 |
introduces a type @{text "('a, 'b, 'c) F"}, three set constants, a map |
2539 |
function, a relator, and a nonemptiness witness that depends only on |
|
2540 |
@{typ 'a}. (The type @{text "'a \<Rightarrow> ('a, 'b, 'c) F"} of |
|
2541 |
the witness can be read as an implication: If we have a witness for @{typ 'a}, |
|
2542 |
we can construct a witness for @{text "('a, 'b, 'c) F"}.) The BNF |
|
2543 |
properties are postulated as axioms. |
|
2544 |
*} |
|
2545 |
||
56942 | 2546 |
bnf_axiomatization (setA: 'a, setB: 'b, setC: 'c) F [wits: "'a \<Rightarrow> ('a, 'b, 'c) F"] |
55350 | 2547 |
|
2548 |
text {* \blankline *} |
|
2549 |
||
2550 |
print_theorems |
|
2551 |
print_bnfs |
|
52794 | 2552 |
|
52824 | 2553 |
|
53617 | 2554 |
subsection {* Command Syntax |
2555 |
\label{ssec:bnf-command-syntax} *} |
|
2556 |
||
2557 |
||
53621 | 2558 |
subsubsection {* \keyw{bnf} |
2559 |
\label{sssec:bnf} *} |
|
52794 | 2560 |
|
53028 | 2561 |
text {* |
53829 | 2562 |
\begin{matharray}{rcl} |
2563 |
@{command_def "bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2564 |
\end{matharray} |
|
2565 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2566 |
@{rail \<open> |
55474 | 2567 |
@@{command bnf} target? (name ':')? type \<newline> |
55029
61a6bf7d4b02
clarified @{rail} syntax: prefer explicit \<newline> symbol;
wenzelm
parents:
54958
diff
changeset
|
2568 |
'map:' term ('sets:' (term +))? 'bd:' term \<newline> |
54421 | 2569 |
('wits:' (term +))? ('rel:' term)? |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2570 |
\<close>} |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2571 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2572 |
\medskip |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2573 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2574 |
\noindent |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2575 |
The @{command bnf} command registers an existing type as a bounded natural |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2576 |
functor (BNF). The type must be equipped with an appropriate map function |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2577 |
(functorial action). In addition, custom set functions, relators, and |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2578 |
nonemptiness witnesses can be specified; otherwise, default versions are used. |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2579 |
|
55474 | 2580 |
The syntactic entity \synt{target} can be used to specify a local context, |
2581 |
\synt{type} denotes a HOL type, and \synt{term} denotes a HOL term |
|
2582 |
\cite{isabelle-isar-ref}. |
|
2583 |
||
2584 |
%%% TODO: elaborate on proof obligations |
|
53028 | 2585 |
*} |
52805 | 2586 |
|
53617 | 2587 |
|
56948 | 2588 |
subsubsection {* \keyw{bnf\_axiomatization} |
2589 |
\label{sssec:bnf-axiomatization} *} |
|
54187 | 2590 |
|
2591 |
text {* |
|
2592 |
\begin{matharray}{rcl} |
|
56942 | 2593 |
@{command_def "bnf_axiomatization"} & : & @{text "local_theory \<rightarrow> local_theory"} |
54187 | 2594 |
\end{matharray} |
2595 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2596 |
@{rail \<open> |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
2597 |
@@{command bnf_axiomatization} target? @{syntax tyargs}? name @{syntax wit_types}? \<newline> |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
2598 |
mixfix? @{syntax map_rel}? |
54602 | 2599 |
; |
55350 | 2600 |
@{syntax_def wit_types}: '[' 'wits' ':' types ']' |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2601 |
\<close>} |
54602 | 2602 |
|
55351 | 2603 |
\medskip |
2604 |
||
55350 | 2605 |
\noindent |
56942 | 2606 |
The @{command bnf_axiomatization} command declares a new type and associated constants |
55350 | 2607 |
(map, set, relator, and cardinal bound) and asserts the BNF properties for |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2608 |
these constants as axioms. |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2609 |
|
55474 | 2610 |
The syntactic entity \synt{target} can be used to specify a local context, |
2611 |
\synt{name} denotes an identifier, \synt{typefree} denotes fixed type variable |
|
2612 |
(@{typ 'a}, @{typ 'b}, \ldots), and \synt{mixfix} denotes the usual |
|
2613 |
parenthesized mixfix notation \cite{isabelle-isar-ref}. |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2614 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2615 |
Type arguments are live by default; they can be marked as dead by entering |
57092 | 2616 |
``@{text dead}'' in front of the type variable (e.g., ``@{text "(dead 'a)"}'') |
2617 |
instead of an identifier for the corresponding set function. Witnesses can be |
|
2618 |
specified by their types. Otherwise, the syntax of @{command bnf_axiomatization} |
|
2619 |
is identical to the left-hand side of a @{command datatype_new} or |
|
2620 |
@{command codatatype} definition. |
|
55350 | 2621 |
|
2622 |
The command is useful to reason abstractly about BNFs. The axioms are safe |
|
2623 |
because there exists BNFs of arbitrary large arities. Applications must import |
|
56942 | 2624 |
the theory @{theory BNF_Axiomatization}, located in the directory |
55350 | 2625 |
\verb|~~/src/HOL/Library|, to use this functionality. |
54187 | 2626 |
*} |
2627 |
||
2628 |
||
53621 | 2629 |
subsubsection {* \keyw{print\_bnfs} |
2630 |
\label{sssec:print-bnfs} *} |
|
53617 | 2631 |
|
2632 |
text {* |
|
53829 | 2633 |
\begin{matharray}{rcl} |
2634 |
@{command_def "print_bnfs"} & : & @{text "local_theory \<rightarrow>"} |
|
2635 |
\end{matharray} |
|
2636 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2637 |
@{rail \<open> |
53829 | 2638 |
@@{command print_bnfs} |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2639 |
\<close>} |
53617 | 2640 |
*} |
2641 |
||
2642 |
||
2643 |
section {* Deriving Destructors and Theorems for Free Constructors |
|
2644 |
\label{sec:deriving-destructors-and-theorems-for-free-constructors} *} |
|
52794 | 2645 |
|
52805 | 2646 |
text {* |
53623 | 2647 |
The derivation of convenience theorems for types equipped with free constructors, |
53829 | 2648 |
as performed internally by @{command datatype_new} and @{command codatatype}, |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
2649 |
is available as a stand-alone command called @{command free_constructors}. |
52794 | 2650 |
|
53617 | 2651 |
% * need for this is rare but may arise if you want e.g. to add destructors to |
2652 |
% a type not introduced by ... |
|
2653 |
% |
|
2654 |
% * also useful for compatibility with old package, e.g. add destructors to |
|
2655 |
% old \keyw{datatype} |
|
2656 |
% |
|
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
2657 |
% * @{command free_constructors} |
55410 | 2658 |
% * @{text "no_discs_sels"}, @{text "no_code"} |
53617 | 2659 |
% * hack to have both co and nonco view via locale (cf. ext nats) |
54616 | 2660 |
% * code generator |
2661 |
% * eq, refl, simps |
|
52805 | 2662 |
*} |
52792 | 2663 |
|
52824 | 2664 |
|
53619 | 2665 |
(* |
53617 | 2666 |
subsection {* Introductory Example |
2667 |
\label{ssec:ctors-introductory-example} *} |
|
53619 | 2668 |
*) |
52794 | 2669 |
|
52824 | 2670 |
|
53617 | 2671 |
subsection {* Command Syntax |
2672 |
\label{ssec:ctors-command-syntax} *} |
|
2673 |
||
2674 |
||
55472
990651bfc65b
updated docs to reflect the new 'free_constructors' syntax
blanchet
parents:
55468
diff
changeset
|
2675 |
subsubsection {* \keyw{free\_constructors} |
990651bfc65b
updated docs to reflect the new 'free_constructors' syntax
blanchet
parents:
55468
diff
changeset
|
2676 |
\label{sssec:free-constructors} *} |
52828 | 2677 |
|
53018 | 2678 |
text {* |
53829 | 2679 |
\begin{matharray}{rcl} |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
2680 |
@{command_def "free_constructors"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
53829 | 2681 |
\end{matharray} |
53018 | 2682 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2683 |
@{rail \<open> |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
2684 |
@@{command free_constructors} target? @{syntax dt_options} \<newline> |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
2685 |
name 'for' (@{syntax fc_ctor} + '|') \<newline> |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
2686 |
(@'where' (prop + '|'))? |
53018 | 2687 |
; |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
2688 |
@{syntax_def fc_ctor}: (name ':')? term (name * ) |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2689 |
\<close>} |
53018 | 2690 |
|
55351 | 2691 |
\medskip |
2692 |
||
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2693 |
\noindent |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2694 |
The @{command free_constructors} command generates destructor constants for |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2695 |
freely constructed types as well as properties about constructors and |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2696 |
destructors. It also registers the constants and theorems in a data structure |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2697 |
that is queried by various tools (e.g., \keyw{function}). |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2698 |
|
55474 | 2699 |
The syntactic entity \synt{target} can be used to specify a local context, |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
2700 |
\synt{name} denotes an identifier, \synt{prop} denotes a HOL proposition, and |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
2701 |
\synt{term} denotes a HOL term \cite{isabelle-isar-ref}. |
55474 | 2702 |
|
2703 |
The syntax resembles that of @{command datatype_new} and @{command codatatype} |
|
2704 |
definitions (Sections |
|
2705 |
\ref{ssec:datatype-command-syntax}~and~\ref{ssec:codatatype-command-syntax}). |
|
2706 |
A constructor is specified by an optional name for the discriminator, the |
|
2707 |
constructor itself (as a term), and a list of optional names for the selectors. |
|
53028 | 2708 |
|
53542 | 2709 |
Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems. |
55398 | 2710 |
For technical reasons, the @{text "[fundef_cong]"} attribute is not set on the |
2711 |
generated @{text case_cong} theorem. It can be added manually using |
|
2712 |
\keyw{declare}. |
|
53018 | 2713 |
*} |
52828 | 2714 |
|
52794 | 2715 |
|
53617 | 2716 |
(* |
52827 | 2717 |
section {* Standard ML Interface |
52805 | 2718 |
\label{sec:standard-ml-interface} *} |
52792 | 2719 |
|
52805 | 2720 |
text {* |
53623 | 2721 |
The package's programmatic interface. |
52805 | 2722 |
*} |
53617 | 2723 |
*) |
52794 | 2724 |
|
2725 |
||
53617 | 2726 |
(* |
52827 | 2727 |
section {* Interoperability |
52805 | 2728 |
\label{sec:interoperability} *} |
52794 | 2729 |
|
52805 | 2730 |
text {* |
53623 | 2731 |
The package's interaction with other Isabelle packages and tools, such as the |
2732 |
code generator and the counterexample generators. |
|
52805 | 2733 |
*} |
52794 | 2734 |
|
52824 | 2735 |
|
52828 | 2736 |
subsection {* Transfer and Lifting |
2737 |
\label{ssec:transfer-and-lifting} *} |
|
52794 | 2738 |
|
52824 | 2739 |
|
52828 | 2740 |
subsection {* Code Generator |
2741 |
\label{ssec:code-generator} *} |
|
52794 | 2742 |
|
52824 | 2743 |
|
52828 | 2744 |
subsection {* Quickcheck |
2745 |
\label{ssec:quickcheck} *} |
|
52794 | 2746 |
|
52824 | 2747 |
|
52828 | 2748 |
subsection {* Nitpick |
2749 |
\label{ssec:nitpick} *} |
|
52794 | 2750 |
|
52824 | 2751 |
|
52828 | 2752 |
subsection {* Nominal Isabelle |
2753 |
\label{ssec:nominal-isabelle} *} |
|
53617 | 2754 |
*) |
52794 | 2755 |
|
52805 | 2756 |
|
53617 | 2757 |
(* |
52827 | 2758 |
section {* Known Bugs and Limitations |
52805 | 2759 |
\label{sec:known-bugs-and-limitations} *} |
2760 |
||
2761 |
text {* |
|
53623 | 2762 |
Known open issues of the package. |
52805 | 2763 |
*} |
52794 | 2764 |
|
2765 |
text {* |
|
53617 | 2766 |
%* slow n-ary mutual (co)datatype, avoid as much as possible (e.g. using nesting) |
2767 |
% |
|
2768 |
%* partial documentation |
|
2769 |
% |
|
2770 |
%* no way to register "sum" and "prod" as (co)datatypes to enable N2M reduction for them |
|
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
2771 |
% (for @{command datatype_compat} and prim(co)rec) |
53617 | 2772 |
% |
53619 | 2773 |
% * a fortiori, no way to register same type as both data- and codatatype |
53617 | 2774 |
% |
2775 |
%* no recursion through unused arguments (unlike with the old package) |
|
2776 |
% |
|
2777 |
%* in a locale, cannot use locally fixed types (because of limitation in typedef)? |
|
53619 | 2778 |
% |
2779 |
% *names of variables suboptimal |
|
52822 | 2780 |
*} |
53675 | 2781 |
*) |
52822 | 2782 |
|
2783 |
||
2784 |
text {* |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
2785 |
\section*{Acknowledgment} |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
2786 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2787 |
Tobias Nipkow and Makarius Wenzel encouraged us to implement the new |
53617 | 2788 |
(co)datatype package. Andreas Lochbihler provided lots of comments on earlier |
56655 | 2789 |
versions of the package, especially on the coinductive part. Brian Huffman |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
2790 |
suggested major simplifications to the internal constructions, many of which |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
2791 |
have yet to be implemented. Florian Haftmann and Christian Urban provided |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
2792 |
general advice on Isabelle and package writing. Stefan Milius and Lutz |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
2793 |
Schr\"oder found an elegant proof that eliminated one of the BNF proof |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
2794 |
obligations. Andreas Lochbihler and Christian Sternagel suggested many textual |
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
2795 |
improvements to this tutorial. |
52794 | 2796 |
*} |
53617 | 2797 |
|
52792 | 2798 |
end |