author | traytel |
Wed, 17 Feb 2016 15:18:06 +0100 | |
changeset 62330 | 7d0c92d5dd80 |
parent 62328 | 532ad8de5d61 |
child 62331 | e923f200bda5 |
permissions | -rw-r--r-- |
52792 | 1 |
(* Title: Doc/Datatypes/Datatypes.thy |
61303 | 2 |
Author: Julian Biendarra, TU Muenchen |
52792 | 3 |
Author: Jasmin Blanchette, TU Muenchen |
57079 | 4 |
Author: Martin Desharnais, Ecole de technologie superieure |
53617 | 5 |
Author: Lorenz Panny, TU Muenchen |
6 |
Author: Andrei Popescu, TU Muenchen |
|
7 |
Author: Dmitriy Traytel, TU Muenchen |
|
52792 | 8 |
|
58305
57752a91eec4
renamed 'datatype' to 'old_datatype'; 'datatype' is now alias for 'datatype_new'
blanchet
parents:
58298
diff
changeset
|
9 |
Tutorial for (co)datatype definitions. |
52792 | 10 |
*) |
11 |
||
12 |
theory Datatypes |
|
55073 | 13 |
imports |
14 |
Setup |
|
56942 | 15 |
"~~/src/HOL/Library/BNF_Axiomatization" |
55350 | 16 |
"~~/src/HOL/Library/Cardinal_Notations" |
62081 | 17 |
"~~/src/HOL/Library/Countable" |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
18 |
"~~/src/HOL/Library/FSet" |
55073 | 19 |
"~~/src/HOL/Library/Simps_Case_Conv" |
52792 | 20 |
begin |
21 |
||
62081 | 22 |
section \<open> Introduction |
23 |
\label{sec:introduction} \<close> |
|
24 |
||
25 |
text \<open> |
|
58305
57752a91eec4
renamed 'datatype' to 'old_datatype'; 'datatype' is now alias for 'datatype_new'
blanchet
parents:
58298
diff
changeset
|
26 |
The 2013 edition of Isabelle introduced a definitional package for freely |
57752a91eec4
renamed 'datatype' to 'old_datatype'; 'datatype' is now alias for 'datatype_new'
blanchet
parents:
58298
diff
changeset
|
27 |
generated datatypes and codatatypes. This package replaces the earlier |
58620 | 28 |
implementation due to Berghofer and Wenzel @{cite "Berghofer-Wenzel:1999:TPHOL"}. |
52841 | 29 |
Perhaps the main advantage of the new package is that it supports recursion |
53619 | 30 |
through a large class of non-datatypes, such as finite sets: |
62081 | 31 |
\<close> |
52792 | 32 |
|
58310 | 33 |
datatype '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 | 34 |
|
62081 | 35 |
text \<open> |
52794 | 36 |
\noindent |
53025 | 37 |
Another strong point is the support for local definitions: |
62081 | 38 |
\<close> |
52792 | 39 |
|
52805 | 40 |
context linorder |
41 |
begin |
|
58310 | 42 |
datatype flag = Less | Eq | Greater |
52805 | 43 |
end |
52792 | 44 |
|
62081 | 45 |
text \<open> |
52794 | 46 |
\noindent |
54187 | 47 |
Furthermore, the package provides a lot of convenience, including automatically |
48 |
generated discriminators, selectors, and relators as well as a wealth of |
|
49 |
properties about them. |
|
50 |
||
58305
57752a91eec4
renamed 'datatype' to 'old_datatype'; 'datatype' is now alias for 'datatype_new'
blanchet
parents:
58298
diff
changeset
|
51 |
In addition to inductive datatypes, the package supports coinductive |
54187 | 52 |
datatypes, or \emph{codatatypes}, which allow infinite values. For example, the |
53 |
following command introduces the type of lazy lists, which comprises both finite |
|
54 |
and infinite values: |
|
62081 | 55 |
\<close> |
52794 | 56 |
|
53623 | 57 |
(*<*) |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
58 |
locale early |
54072 | 59 |
locale late |
53623 | 60 |
(*>*) |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
61 |
codatatype (*<*)(in early) (*>*)'a llist = LNil | LCons 'a "'a llist" |
52794 | 62 |
|
62081 | 63 |
text \<open> |
52794 | 64 |
\noindent |
52840 | 65 |
Mixed inductive--coinductive recursion is possible via nesting. Compare the |
53028 | 66 |
following four Rose tree examples: |
62081 | 67 |
\<close> |
52794 | 68 |
|
58310 | 69 |
datatype (*<*)(in early) (*>*)'a tree\<^sub>f\<^sub>f = Node\<^sub>f\<^sub>f 'a "'a tree\<^sub>f\<^sub>f list" |
70 |
datatype (*<*)(in early) (*>*)'a tree\<^sub>f\<^sub>i = Node\<^sub>f\<^sub>i 'a "'a tree\<^sub>f\<^sub>i llist" |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
71 |
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
|
72 |
codatatype (*<*)(in early) (*>*)'a tree\<^sub>i\<^sub>i = Node\<^sub>i\<^sub>i 'a "'a tree\<^sub>i\<^sub>i llist" |
52792 | 73 |
|
62081 | 74 |
text \<open> |
54187 | 75 |
The first two tree types allow only paths of finite length, whereas the last two |
76 |
allow infinite paths. Orthogonally, the nodes in the first and third types have |
|
77 |
finitely many direct subtrees, whereas those of the second and fourth may have |
|
78 |
infinite branching. |
|
52840 | 79 |
|
55073 | 80 |
The package is part of @{theory Main}. Additional functionality is provided by |
61304 | 81 |
the theory @{file "~~/src/HOL/Library/BNF_Axiomatization.thy"}. |
55073 | 82 |
|
52805 | 83 |
The package, like its predecessor, fully adheres to the LCF philosophy |
58620 | 84 |
@{cite mgordon79}: The characteristic theorems associated with the specified |
52805 | 85 |
(co)datatypes are derived rather than introduced axiomatically.% |
57542 | 86 |
\footnote{However, some of the |
58298 | 87 |
internal constructions and most of the internal proof obligations are omitted |
57542 | 88 |
if the @{text quick_and_dirty} option is enabled.} |
57575 | 89 |
The package is described in a number of papers |
60146 | 90 |
@{cite "traytel-et-al-2012" and "blanchette-et-al-2014-impl" and |
91 |
"panny-et-al-2014" and "blanchette-et-al-2015-wit"}. |
|
57542 | 92 |
The central notion is that of a \emph{bounded natural functor} (BNF)---a |
93 |
well-behaved type constructor for which nested (co)recursion is supported. |
|
52792 | 94 |
|
52794 | 95 |
This tutorial is organized as follows: |
96 |
||
52805 | 97 |
\begin{itemize} |
52822 | 98 |
\setlength{\itemsep}{0pt} |
99 |
||
52805 | 100 |
\item Section \ref{sec:defining-datatypes}, ``Defining Datatypes,'' |
58310 | 101 |
describes how to specify datatypes using the @{command datatype} command. |
52805 | 102 |
|
59861 | 103 |
\item Section \ref{sec:defining-primitively-recursive-functions}, ``Defining |
60192 | 104 |
Primitively Recursive Functions,'' describes how to specify functions |
59861 | 105 |
using @{command primrec}. (A separate tutorial @{cite "isabelle-function"} |
106 |
describes the more general \keyw{fun} and \keyw{function} commands.) |
|
52805 | 107 |
|
108 |
\item Section \ref{sec:defining-codatatypes}, ``Defining Codatatypes,'' |
|
53829 | 109 |
describes how to specify codatatypes using the @{command codatatype} command. |
52805 | 110 |
|
59861 | 111 |
\item Section \ref{sec:defining-primitively-corecursive-functions}, |
112 |
``Defining Primitively Corecursive Functions,'' describes how to specify |
|
60192 | 113 |
functions using the @{command primcorec} and |
59861 | 114 |
@{command primcorecursive} commands. |
52794 | 115 |
|
59298 | 116 |
\item Section \ref{sec:registering-bounded-natural-functors}, ``Registering |
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 |
58311 | 124 |
and theorems for freely generated types, as performed internally by |
125 |
@{command datatype} and @{command codatatype}. |
|
52794 | 126 |
|
58245 | 127 |
%\item Section \ref{sec:using-the-standard-ml-interface}, ``Using the Standard |
60192 | 128 |
%ML Interface,'' describes the package's programmatic interface. |
58245 | 129 |
|
59282 | 130 |
\item Section \ref{sec:selecting-plugins}, ``Selecting Plugins,'' is concerned |
131 |
with the package's interoperability with other Isabelle packages and tools, such |
|
132 |
as the code generator, Transfer, Lifting, and Quickcheck. |
|
52805 | 133 |
|
58395 | 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 |
\newbox\boxA |
|
54185 | 139 |
\setbox\boxA=\hbox{\texttt{NOSPAM}} |
140 |
||
141 |
\newcommand\authoremaili{\texttt{blan{\color{white}NOSPAM}\kern-\wd\boxA{}chette@\allowbreak |
|
52822 | 142 |
in.\allowbreak tum.\allowbreak de}} |
143 |
||
58305
57752a91eec4
renamed 'datatype' to 'old_datatype'; 'datatype' is now alias for 'datatype_new'
blanchet
parents:
58298
diff
changeset
|
144 |
Comments and bug reports concerning either the package or this tutorial should |
61788 | 145 |
be directed to the first author at \authoremaili{} or to the |
60146 | 146 |
\texttt{cl-isabelle-users} mailing list. |
62081 | 147 |
\<close> |
148 |
||
149 |
||
150 |
section \<open> Defining Datatypes |
|
151 |
\label{sec:defining-datatypes} \<close> |
|
152 |
||
153 |
text \<open> |
|
58310 | 154 |
Datatypes can be specified using the @{command datatype} command. |
62081 | 155 |
\<close> |
156 |
||
157 |
||
158 |
subsection \<open> Introductory Examples |
|
159 |
\label{ssec:datatype-introductory-examples} \<close> |
|
160 |
||
161 |
text \<open> |
|
53646 | 162 |
Datatypes are illustrated through concrete examples featuring different flavors |
163 |
of recursion. More examples can be found in the directory |
|
61304 | 164 |
@{file "~~/src/HOL/Datatype_Examples"} |
62081 | 165 |
\<close> |
166 |
||
167 |
||
168 |
subsubsection \<open> Nonrecursive Types |
|
169 |
\label{sssec:datatype-nonrecursive-types} \<close> |
|
170 |
||
171 |
text \<open> |
|
53028 | 172 |
Datatypes are introduced by specifying the desired names and argument types for |
53491 | 173 |
their constructors. \emph{Enumeration} types are the simplest form of datatype. |
53028 | 174 |
All their constructors are nullary: |
62081 | 175 |
\<close> |
52805 | 176 |
|
58310 | 177 |
datatype trool = Truue | Faalse | Perhaaps |
52805 | 178 |
|
62081 | 179 |
text \<open> |
53028 | 180 |
\noindent |
59282 | 181 |
@{const Truue}, @{const Faalse}, and @{const Perhaaps} have the type @{typ trool}. |
53028 | 182 |
|
183 |
Polymorphic types are possible, such as the following option type, modeled after |
|
184 |
its homologue from the @{theory Option} theory: |
|
62081 | 185 |
\<close> |
52805 | 186 |
|
53025 | 187 |
(*<*) |
56995 | 188 |
hide_const None Some map_option |
54958
4933165fd112
do not use wrong constructor in auto-generated proof goal
panny
parents:
54955
diff
changeset
|
189 |
hide_type option |
53025 | 190 |
(*>*) |
58310 | 191 |
datatype 'a option = None | Some 'a |
52805 | 192 |
|
62081 | 193 |
text \<open> |
53028 | 194 |
\noindent |
61076 | 195 |
The constructors are @{text "None :: 'a option"} and |
196 |
@{text "Some :: 'a \<Rightarrow> 'a option"}. |
|
53028 | 197 |
|
198 |
The next example has three type parameters: |
|
62081 | 199 |
\<close> |
52805 | 200 |
|
58310 | 201 |
datatype ('a, 'b, 'c) triple = Triple 'a 'b 'c |
52805 | 202 |
|
62081 | 203 |
text \<open> |
53028 | 204 |
\noindent |
205 |
The constructor is |
|
61076 | 206 |
@{text "Triple :: 'a \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> ('a, 'b, 'c) triple"}. |
53028 | 207 |
Unlike in Standard ML, curried constructors are supported. The uncurried variant |
208 |
is also possible: |
|
62081 | 209 |
\<close> |
53028 | 210 |
|
58310 | 211 |
datatype ('a, 'b, 'c) triple\<^sub>u = Triple\<^sub>u "'a * 'b * 'c" |
53028 | 212 |
|
62081 | 213 |
text \<open> |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
214 |
\noindent |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
215 |
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
|
216 |
enclosed in double quotes, as is customary in Isabelle. |
62081 | 217 |
\<close> |
218 |
||
219 |
||
220 |
subsubsection \<open> Simple Recursion |
|
221 |
\label{sssec:datatype-simple-recursion} \<close> |
|
222 |
||
223 |
text \<open> |
|
53491 | 224 |
Natural numbers are the simplest example of a recursive type: |
62081 | 225 |
\<close> |
52805 | 226 |
|
58310 | 227 |
datatype nat = Zero | Succ nat |
52805 | 228 |
|
62081 | 229 |
text \<open> |
53491 | 230 |
\noindent |
54187 | 231 |
Lists were shown in the introduction. Terminated lists are a variant that |
232 |
stores a value of type @{typ 'b} at the very end: |
|
62081 | 233 |
\<close> |
52805 | 234 |
|
58310 | 235 |
datatype (*<*)(in early) (*>*)('a, 'b) tlist = TNil 'b | TCons 'a "('a, 'b) tlist" |
52805 | 236 |
|
52824 | 237 |
|
62081 | 238 |
subsubsection \<open> Mutual Recursion |
239 |
\label{sssec:datatype-mutual-recursion} \<close> |
|
240 |
||
241 |
text \<open> |
|
53552 | 242 |
\emph{Mutually recursive} types are introduced simultaneously and may refer to |
243 |
each other. The example below introduces a pair of types for even and odd |
|
244 |
natural numbers: |
|
62081 | 245 |
\<close> |
52805 | 246 |
|
58310 | 247 |
datatype even_nat = Even_Zero | Even_Succ odd_nat |
58245 | 248 |
and odd_nat = Odd_Succ even_nat |
52805 | 249 |
|
62081 | 250 |
text \<open> |
53491 | 251 |
\noindent |
252 |
Arithmetic expressions are defined via terms, terms via factors, and factors via |
|
253 |
expressions: |
|
62081 | 254 |
\<close> |
52805 | 255 |
|
58310 | 256 |
datatype ('a, 'b) exp = |
52841 | 257 |
Term "('a, 'b) trm" | Sum "('a, 'b) trm" "('a, 'b) exp" |
52805 | 258 |
and ('a, 'b) trm = |
52841 | 259 |
Factor "('a, 'b) fct" | Prod "('a, 'b) fct" "('a, 'b) trm" |
260 |
and ('a, 'b) fct = |
|
261 |
Const 'a | Var 'b | Expr "('a, 'b) exp" |
|
52805 | 262 |
|
52824 | 263 |
|
62081 | 264 |
subsubsection \<open> Nested Recursion |
265 |
\label{sssec:datatype-nested-recursion} \<close> |
|
266 |
||
267 |
text \<open> |
|
53491 | 268 |
\emph{Nested recursion} occurs when recursive occurrences of a type appear under |
269 |
a type constructor. The introduction showed some examples of trees with nesting |
|
53675 | 270 |
through lists. A more complex example, that reuses our @{type option} type, |
53491 | 271 |
follows: |
62081 | 272 |
\<close> |
52805 | 273 |
|
58310 | 274 |
datatype 'a btree = |
53025 | 275 |
BNode 'a "'a btree option" "'a btree option" |
52805 | 276 |
|
62081 | 277 |
text \<open> |
53491 | 278 |
\noindent |
279 |
Not all nestings are admissible. For example, this command will fail: |
|
62081 | 280 |
\<close> |
52805 | 281 |
|
58310 | 282 |
datatype 'a wrong = W1 | W2 (*<*)'a |
53542 | 283 |
typ (*>*)"'a wrong \<Rightarrow> 'a" |
52806 | 284 |
|
62081 | 285 |
text \<open> |
53491 | 286 |
\noindent |
287 |
The issue is that the function arrow @{text "\<Rightarrow>"} allows recursion |
|
288 |
only through its right-hand side. This issue is inherited by polymorphic |
|
289 |
datatypes defined in terms of~@{text "\<Rightarrow>"}: |
|
62081 | 290 |
\<close> |
53491 | 291 |
|
58310 | 292 |
datatype ('a, 'b) fun_copy = Fun "'a \<Rightarrow> 'b" |
293 |
datatype 'a also_wrong = W1 | W2 (*<*)'a |
|
55350 | 294 |
typ (*>*)"('a also_wrong, 'a) fun_copy" |
53491 | 295 |
|
62081 | 296 |
text \<open> |
53491 | 297 |
\noindent |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
298 |
The following definition of @{typ 'a}-branching trees is legal: |
62081 | 299 |
\<close> |
53621 | 300 |
|
58310 | 301 |
datatype 'a ftree = FTLeaf 'a | FTNode "'a \<Rightarrow> 'a ftree" |
53621 | 302 |
|
62081 | 303 |
text \<open> |
53621 | 304 |
\noindent |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
305 |
And so is the definition of hereditarily finite sets: |
62081 | 306 |
\<close> |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
307 |
|
58310 | 308 |
datatype hfset = HFSet "hfset fset" |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
309 |
|
62081 | 310 |
text \<open> |
55129
26bd1cba3ab5
killed 'More_BNFs' by moving its various bits where they (now) belong
blanchet
parents:
55114
diff
changeset
|
311 |
\noindent |
53491 | 312 |
In general, type constructors @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
313 |
allow recursion on a subset of their type arguments @{text 'a\<^sub>1}, \ldots, |
|
314 |
@{text 'a\<^sub>m}. These type arguments are called \emph{live}; the remaining |
|
315 |
type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and |
|
55350 | 316 |
@{typ "('a, 'b) fun_copy"}, the type variable @{typ 'a} is dead and |
317 |
@{typ 'b} is live. |
|
53552 | 318 |
|
53647 | 319 |
Type constructors must be registered as BNFs to have live arguments. This is |
58311 | 320 |
done automatically for datatypes and codatatypes introduced by the |
321 |
@{command datatype} and @{command codatatype} commands. |
|
59298 | 322 |
Section~\ref{sec:registering-bounded-natural-functors} explains how to |
55351 | 323 |
register arbitrary type constructors as BNFs. |
54187 | 324 |
|
325 |
Here is another example that fails: |
|
62081 | 326 |
\<close> |
52806 | 327 |
|
58310 | 328 |
datatype 'a pow_list = PNil 'a (*<*)'a |
329 |
datatype 'a pow_list' = PNil' 'a (*>*)| PCons "('a * 'a) pow_list" |
|
54187 | 330 |
|
62081 | 331 |
text \<open> |
54187 | 332 |
\noindent |
55351 | 333 |
This attempted definition features a different flavor of nesting, where the |
334 |
recursive call in the type specification occurs around (rather than inside) |
|
335 |
another type constructor. |
|
62081 | 336 |
\<close> |
337 |
||
338 |
||
339 |
subsubsection \<open> Auxiliary Constants |
|
340 |
\label{sssec:datatype-auxiliary-constants} \<close> |
|
341 |
||
342 |
text \<open> |
|
58310 | 343 |
The @{command datatype} command introduces various constants in addition to |
53617 | 344 |
the constructors. With each datatype are associated set functions, a map |
62330 | 345 |
function,, a predicator, a relator, discriminators, and selectors, all of which can be given |
54187 | 346 |
custom names. In the example below, the familiar names @{text null}, @{text hd}, |
59284 | 347 |
@{text tl}, @{text set}, @{text map}, and @{text list_all2} override the |
54187 | 348 |
default names @{text is_Nil}, @{text un_Cons1}, @{text un_Cons2}, |
54491 | 349 |
@{text set_list}, @{text map_list}, and @{text rel_list}: |
62081 | 350 |
\<close> |
52822 | 351 |
|
52841 | 352 |
(*<*) |
353 |
no_translations |
|
354 |
"[x, xs]" == "x # [xs]" |
|
355 |
"[x]" == "x # []" |
|
356 |
||
357 |
no_notation |
|
358 |
Nil ("[]") and |
|
359 |
Cons (infixr "#" 65) |
|
360 |
||
53543 | 361 |
hide_type list |
62328 | 362 |
hide_const Nil Cons case_list hd tl set map list_all2 rec_list size_list list_all |
53025 | 363 |
|
59284 | 364 |
context early |
365 |
begin |
|
52841 | 366 |
(*>*) |
58310 | 367 |
datatype (set: 'a) list = |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
368 |
null: Nil |
53025 | 369 |
| Cons (hd: 'a) (tl: "'a list") |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
370 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
371 |
map: map |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
372 |
rel: list_all2 |
62328 | 373 |
pred: list_all |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
374 |
where |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
375 |
"tl Nil = Nil" |
52822 | 376 |
|
62081 | 377 |
text \<open> |
52822 | 378 |
\noindent |
55353 | 379 |
The types of the constants that appear in the specification are listed below. |
55351 | 380 |
|
381 |
\medskip |
|
54187 | 382 |
|
383 |
\begin{tabular}{@ {}ll@ {}} |
|
384 |
Constructors: & |
|
61076 | 385 |
@{text "Nil :: 'a list"} \\ |
54187 | 386 |
& |
61076 | 387 |
@{text "Cons :: 'a \<Rightarrow> 'a list \<Rightarrow> 'a list"} \\ |
54187 | 388 |
Discriminator: & |
61076 | 389 |
@{text "null :: 'a list \<Rightarrow> bool"} \\ |
54187 | 390 |
Selectors: & |
61076 | 391 |
@{text "hd :: 'a list \<Rightarrow> 'a"} \\ |
54187 | 392 |
& |
61076 | 393 |
@{text "tl :: 'a list \<Rightarrow> 'a list"} \\ |
54187 | 394 |
Set function: & |
61076 | 395 |
@{text "set :: 'a list \<Rightarrow> 'a set"} \\ |
54187 | 396 |
Map function: & |
61076 | 397 |
@{text "map :: ('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list"} \\ |
54187 | 398 |
Relator: & |
61076 | 399 |
@{text "list_all2 :: ('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> 'a list \<Rightarrow> 'b list \<Rightarrow> bool"} |
54187 | 400 |
\end{tabular} |
401 |
||
55351 | 402 |
\medskip |
403 |
||
54187 | 404 |
The discriminator @{const null} and the selectors @{const hd} and @{const tl} |
55351 | 405 |
are characterized by the following conditional equations: |
52822 | 406 |
% |
53025 | 407 |
\[@{thm list.collapse(1)[of xs, no_vars]} |
408 |
\qquad @{thm list.collapse(2)[of xs, no_vars]}\] |
|
52822 | 409 |
% |
54187 | 410 |
For two-constructor datatypes, a single discriminator constant is sufficient. |
411 |
The discriminator associated with @{const Cons} is simply |
|
53491 | 412 |
@{term "\<lambda>xs. \<not> null xs"}. |
52822 | 413 |
|
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
414 |
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
|
415 |
selectors applied to constructors on which they are not a priori specified. |
59282 | 416 |
In the example, it is used to ensure that the tail of the empty list is itself |
417 |
(instead of being left unspecified). |
|
52822 | 418 |
|
53617 | 419 |
Because @{const Nil} is nullary, it is also possible to use |
57091 | 420 |
@{term "\<lambda>xs. xs = Nil"} as a discriminator. This is the default behavior |
421 |
if we omit the identifier @{const null} and the associated colon. Some users |
|
422 |
argue against this, because the mixture of constructors and selectors in the |
|
423 |
characteristic theorems can lead Isabelle's automation to switch between the |
|
424 |
constructor and the destructor view in surprising ways. |
|
52822 | 425 |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
426 |
The usual mixfix syntax annotations are available for both types and |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
427 |
constructors. For example: |
62081 | 428 |
\<close> |
52794 | 429 |
|
53025 | 430 |
(*<*) |
431 |
end |
|
432 |
(*>*) |
|
58310 | 433 |
datatype ('a, 'b) prod (infixr "*" 20) = Pair 'a 'b |
53552 | 434 |
|
62081 | 435 |
text \<open> \blankline \<close> |
52822 | 436 |
|
58310 | 437 |
datatype (set: 'a) list = |
52822 | 438 |
null: Nil ("[]") |
52841 | 439 |
| 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
|
440 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
441 |
map: map |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
442 |
rel: list_all2 |
62328 | 443 |
pred: list_all |
52841 | 444 |
|
62081 | 445 |
text \<open> |
53535 | 446 |
\noindent |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
447 |
Incidentally, this is how the traditional syntax can be set up: |
62081 | 448 |
\<close> |
52841 | 449 |
|
450 |
syntax "_list" :: "args \<Rightarrow> 'a list" ("[(_)]") |
|
451 |
||
62081 | 452 |
text \<open> \blankline \<close> |
53552 | 453 |
|
52841 | 454 |
translations |
455 |
"[x, xs]" == "x # [xs]" |
|
456 |
"[x]" == "x # []" |
|
52822 | 457 |
|
52824 | 458 |
|
62081 | 459 |
subsection \<open> Command Syntax |
460 |
\label{ssec:datatype-command-syntax} \<close> |
|
461 |
||
462 |
subsubsection \<open> \keyw{datatype} |
|
463 |
\label{sssec:datatype-new} \<close> |
|
464 |
||
465 |
text \<open> |
|
53829 | 466 |
\begin{matharray}{rcl} |
58310 | 467 |
@{command_def "datatype"} & : & @{text "local_theory \<rightarrow> local_theory"} |
53829 | 468 |
\end{matharray} |
52822 | 469 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
470 |
@{rail \<open> |
59282 | 471 |
@@{command datatype} target? @{syntax dt_options}? @{syntax dt_spec} |
52828 | 472 |
; |
59280 | 473 |
@{syntax_def dt_options}: '(' ((@{syntax plugins} | 'discs_sels') + ',') ')' |
58190 | 474 |
; |
59280 | 475 |
@{syntax_def plugins}: 'plugins' ('only' | 'del') ':' (name +) |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
476 |
; |
59282 | 477 |
@{syntax_def dt_spec}: (@{syntax dt_name} '=' (@{syntax dt_ctor} + '|') \<newline> |
478 |
@{syntax map_rel}? (@'where' (prop + '|'))? + @'and') |
|
479 |
; |
|
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
480 |
@{syntax_def map_rel}: @'for' ((('map' | 'rel') ':' name) +) |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
481 |
\<close>} |
52824 | 482 |
|
55351 | 483 |
\medskip |
484 |
||
485 |
\noindent |
|
58310 | 486 |
The @{command datatype} command introduces a set of mutually recursive |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
487 |
datatypes specified by their constructors. |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
488 |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
489 |
The syntactic entity \synt{target} can be used to specify a local |
58620 | 490 |
context (e.g., @{text "(in linorder)"} @{cite "isabelle-isar-ref"}), |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
491 |
and \synt{prop} denotes a HOL proposition. |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
492 |
|
58190 | 493 |
The optional target is optionally followed by a combination of the following |
56124 | 494 |
options: |
52822 | 495 |
|
52824 | 496 |
\begin{itemize} |
497 |
\setlength{\itemsep}{0pt} |
|
498 |
||
499 |
\item |
|
59280 | 500 |
The @{text plugins} option indicates which plugins should be enabled |
501 |
(@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
|
58190 | 502 |
|
503 |
\item |
|
57094
589ec121ce1a
don't generate discriminators and selectors for 'datatype_new' unless the user asked for it
blanchet
parents:
57092
diff
changeset
|
504 |
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
|
505 |
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
|
506 |
discriminators or selectors. |
52824 | 507 |
\end{itemize} |
52822 | 508 |
|
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
509 |
The optional \keyw{where} clause specifies default values for selectors. |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
510 |
Each proposition must be an equation of the form |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
511 |
@{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
|
512 |
@{text un_D} is a selector. |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
513 |
|
52827 | 514 |
The left-hand sides of the datatype equations specify the name of the type to |
53534 | 515 |
define, its type parameters, and additional information: |
52822 | 516 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
517 |
@{rail \<open> |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
518 |
@{syntax_def dt_name}: @{syntax tyargs}? name mixfix? |
52824 | 519 |
; |
57092 | 520 |
@{syntax_def tyargs}: typefree | '(' (('dead' | name ':')? typefree + ',') ')' |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
521 |
\<close>} |
52822 | 522 |
|
55351 | 523 |
\medskip |
524 |
||
52827 | 525 |
\noindent |
55474 | 526 |
The syntactic entity \synt{name} denotes an identifier, \synt{mixfix} denotes |
527 |
the usual parenthesized mixfix notation, and \synt{typefree} denotes fixed type |
|
58620 | 528 |
variable (@{typ 'a}, @{typ 'b}, \ldots) @{cite "isabelle-isar-ref"}. |
52822 | 529 |
|
52827 | 530 |
The optional names preceding the type variables allow to override the default |
57988 | 531 |
names of the set functions (@{text set\<^sub>1_t}, \ldots, @{text set\<^sub>m_t}). Type |
58190 | 532 |
arguments can be marked as dead by entering @{text dead} in front of the |
58220 | 533 |
type variable (e.g., @{text "(dead 'a)"}); otherwise, they are live or dead |
55705 | 534 |
(and a set function is generated or not) depending on where they occur in the |
535 |
right-hand sides of the definition. Declaring a type argument as dead can speed |
|
536 |
up the type definition but will prevent any later (co)recursion through that |
|
537 |
type argument. |
|
538 |
||
53647 | 539 |
Inside a mutually recursive specification, all defined datatypes must |
540 |
mention exactly the same type variables in the same order. |
|
52822 | 541 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
542 |
@{rail \<open> |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
543 |
@{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
|
544 |
\<close>} |
52824 | 545 |
|
53535 | 546 |
\medskip |
547 |
||
52827 | 548 |
\noindent |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
549 |
The main constituents of a constructor specification are the name of the |
52827 | 550 |
constructor and the list of its argument types. An optional discriminator name |
59722 | 551 |
can be supplied at the front. If discriminators are enabled (cf.\ the |
552 |
@{text "discs_sels"} option) but no name is supplied, the default is |
|
57091 | 553 |
@{text "\<lambda>x. x = C\<^sub>j"} for nullary constructors and |
554 |
@{text t.is_C\<^sub>j} otherwise. |
|
52822 | 555 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
556 |
@{rail \<open> |
55472
990651bfc65b
updated docs to reflect the new 'free_constructors' syntax
blanchet
parents:
55468
diff
changeset
|
557 |
@{syntax_def dt_ctor_arg}: type | '(' name ':' type ')' |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
558 |
\<close>} |
52827 | 559 |
|
53535 | 560 |
\medskip |
561 |
||
52827 | 562 |
\noindent |
58620 | 563 |
The syntactic entity \synt{type} denotes a HOL type @{cite "isabelle-isar-ref"}. |
55474 | 564 |
|
52827 | 565 |
In addition to the type of a constructor argument, it is possible to specify a |
59722 | 566 |
name for the corresponding selector. The same selector name can be reused for |
567 |
arguments to several constructors as long as the arguments share the same type. |
|
568 |
If selectors are enabled (cf.\ the @{text "discs_sels"} option) but no name is |
|
569 |
supplied, the default name is @{text un_C\<^sub>ji}. |
|
62081 | 570 |
\<close> |
571 |
||
572 |
||
573 |
subsubsection \<open> \keyw{datatype_compat} |
|
574 |
\label{sssec:datatype-compat} \<close> |
|
575 |
||
576 |
text \<open> |
|
53829 | 577 |
\begin{matharray}{rcl} |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
578 |
@{command_def "datatype_compat"} & : & @{text "local_theory \<rightarrow> local_theory"} |
53829 | 579 |
\end{matharray} |
580 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
581 |
@{rail \<open> |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
582 |
@@{command datatype_compat} (name +) |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
583 |
\<close>} |
53829 | 584 |
|
55351 | 585 |
\medskip |
586 |
||
53829 | 587 |
\noindent |
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
588 |
The @{command datatype_compat} command registers new-style datatypes as |
58245 | 589 |
old-style datatypes and invokes the old-style plugins. For example: |
62081 | 590 |
\<close> |
53621 | 591 |
|
55531
601ca8efa000
renamed 'datatype_new_compat' to 'datatype_compat'
blanchet
parents:
55530
diff
changeset
|
592 |
datatype_compat even_nat odd_nat |
53621 | 593 |
|
62081 | 594 |
text \<open> \blankline \<close> |
595 |
||
596 |
ML \<open> Old_Datatype_Data.get_info @{theory} @{type_name even_nat} \<close> |
|
597 |
||
598 |
text \<open> |
|
58620 | 599 |
The syntactic entity \synt{name} denotes an identifier @{cite "isabelle-isar-ref"}. |
55474 | 600 |
|
60135
852f7a49ec0c
updated docs, esp. relating to 'datatype_compat'
blanchet
parents:
60134
diff
changeset
|
601 |
The command is sometimes useful when migrating from the old datatype package to |
852f7a49ec0c
updated docs, esp. relating to 'datatype_compat'
blanchet
parents:
60134
diff
changeset
|
602 |
the new one. |
55474 | 603 |
|
604 |
A few remarks concern nested recursive datatypes: |
|
53748 | 605 |
|
606 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
607 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
608 |
|
55871 | 609 |
\item The old-style, nested-as-mutual induction rule and recursor theorems are |
610 |
generated under their usual names but with ``@{text "compat_"}'' prefixed |
|
58215 | 611 |
(e.g., @{text compat_tree.induct}, @{text compat_tree.inducts}, and |
61351 | 612 |
@{text compat_tree.rec}). These theorems should be identical to the ones |
613 |
generated by the old datatype package, \emph{up to the order of the |
|
614 |
premises}---meaning that the subgoals generated by the @{text induct} or |
|
615 |
@{text induction} method may be in a different order than before. |
|
53748 | 616 |
|
617 |
\item All types through which recursion takes place must be new-style datatypes |
|
59722 | 618 |
or the function type. |
53748 | 619 |
\end{itemize} |
62081 | 620 |
\<close> |
621 |
||
622 |
||
623 |
subsection \<open> Generated Constants |
|
624 |
\label{ssec:datatype-generated-constants} \<close> |
|
625 |
||
626 |
text \<open> |
|
59722 | 627 |
Given a datatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} with $m$ live type variables |
59284 | 628 |
and $n$ constructors @{text "t.C\<^sub>1"}, \ldots, @{text "t.C\<^sub>n"}, the following |
629 |
auxiliary constants are introduced: |
|
53617 | 630 |
|
55353 | 631 |
\medskip |
632 |
||
633 |
\begin{tabular}{@ {}ll@ {}} |
|
634 |
Case combinator: & |
|
635 |
@{text t.case_t} (rendered using the familiar @{text case}--@{text of} syntax) \\ |
|
636 |
Discriminators: & |
|
57988 | 637 |
@{text t.is_C\<^sub>1}$, \ldots, $@{text t.is_C\<^sub>n} \\ |
55353 | 638 |
Selectors: & |
639 |
@{text t.un_C\<^sub>11}$, \ldots, $@{text t.un_C\<^sub>1k\<^sub>1} \\ |
|
640 |
& \quad\vdots \\ |
|
641 |
& @{text t.un_C\<^sub>n1}$, \ldots, $@{text t.un_C\<^sub>nk\<^sub>n} \\ |
|
642 |
Set functions: & |
|
57988 | 643 |
@{text t.set\<^sub>1_t}, \ldots, @{text t.set\<^sub>m_t} \\ |
55353 | 644 |
Map function: & |
645 |
@{text t.map_t} \\ |
|
646 |
Relator: & |
|
647 |
@{text t.rel_t} \\ |
|
648 |
Recursor: & |
|
58190 | 649 |
@{text t.rec_t} |
55353 | 650 |
\end{tabular} |
651 |
||
652 |
\medskip |
|
53617 | 653 |
|
654 |
\noindent |
|
59722 | 655 |
The discriminators and selectors are generated only if the @{text "discs_sels"} |
656 |
option is enabled or if names are specified for discriminators or selectors. |
|
62330 | 657 |
The set functions, map function, predicator, and relator are generated only if $m > 0$. |
59722 | 658 |
|
58245 | 659 |
In addition, some of the plugins introduce their own constants |
59282 | 660 |
(Section~\ref{sec:selecting-plugins}). The case combinator, discriminators, |
58508 | 661 |
and selectors are collectively called \emph{destructors}. The prefix |
662 |
``@{text "t."}'' is an optional component of the names and is normally hidden. |
|
62081 | 663 |
\<close> |
664 |
||
665 |
||
666 |
subsection \<open> Generated Theorems |
|
667 |
\label{ssec:datatype-generated-theorems} \<close> |
|
668 |
||
669 |
text \<open> |
|
58310 | 670 |
The characteristic theorems generated by @{command datatype} are grouped in |
53623 | 671 |
three broad categories: |
53535 | 672 |
|
53543 | 673 |
\begin{itemize} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
674 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
675 |
|
56655 | 676 |
\item The \emph{free constructor theorems} |
677 |
(Section~\ref{sssec:free-constructor-theorems}) are properties of the |
|
678 |
constructors and destructors that can be derived for any freely generated type. |
|
679 |
Internally, the derivation is performed by @{command free_constructors}. |
|
680 |
||
681 |
\item The \emph{functorial theorems} (Section~\ref{sssec:functorial-theorems}) |
|
682 |
are properties of datatypes related to their BNF nature. |
|
683 |
||
684 |
\item The \emph{inductive theorems} (Section~\ref{sssec:inductive-theorems}) |
|
685 |
are properties of datatypes related to their inductive nature. |
|
53552 | 686 |
|
53543 | 687 |
\end{itemize} |
53535 | 688 |
|
689 |
\noindent |
|
53542 | 690 |
The full list of named theorems can be obtained as usual by entering the |
57542 | 691 |
command \keyw{print_theorems} immediately after the datatype definition. |
58508 | 692 |
This list includes theorems produced by plugins |
59282 | 693 |
(Section~\ref{sec:selecting-plugins}), but normally excludes low-level |
58508 | 694 |
theorems that reveal internal constructions. To make these accessible, add |
695 |
the line |
|
62081 | 696 |
\<close> |
53535 | 697 |
|
62093 | 698 |
declare [[bnf_internals]] |
53542 | 699 |
(*<*) |
62093 | 700 |
declare [[bnf_internals = false]] |
53542 | 701 |
(*>*) |
53535 | 702 |
|
62081 | 703 |
text \<open> |
53552 | 704 |
\noindent |
705 |
to the top of the theory file. |
|
62081 | 706 |
\<close> |
707 |
||
708 |
||
709 |
subsubsection \<open> Free Constructor Theorems |
|
710 |
\label{sssec:free-constructor-theorems} \<close> |
|
53535 | 711 |
|
53543 | 712 |
(*<*) |
53837 | 713 |
consts nonnull :: 'a |
53543 | 714 |
(*>*) |
715 |
||
62081 | 716 |
text \<open> |
54621 | 717 |
The free constructor theorems are partitioned in three subgroups. The first |
718 |
subgroup of properties is concerned with the constructors. They are listed below |
|
719 |
for @{typ "'a list"}: |
|
53543 | 720 |
|
53552 | 721 |
\begin{indentblock} |
53543 | 722 |
\begin{description} |
53544 | 723 |
|
53642 | 724 |
\item[@{text "t."}\hthm{inject} @{text "[iff, induct_simp]"}\rm:] ~ \\ |
53544 | 725 |
@{thm list.inject[no_vars]} |
726 |
||
53642 | 727 |
\item[@{text "t."}\hthm{distinct} @{text "[simp, induct_simp]"}\rm:] ~ \\ |
53543 | 728 |
@{thm list.distinct(1)[no_vars]} \\ |
729 |
@{thm list.distinct(2)[no_vars]} |
|
730 |
||
53642 | 731 |
\item[@{text "t."}\hthm{exhaust} @{text "[cases t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
53543 | 732 |
@{thm list.exhaust[no_vars]} |
733 |
||
53642 | 734 |
\item[@{text "t."}\hthm{nchotomy}\rm:] ~ \\ |
53543 | 735 |
@{thm list.nchotomy[no_vars]} |
736 |
||
737 |
\end{description} |
|
53552 | 738 |
\end{indentblock} |
53543 | 739 |
|
740 |
\noindent |
|
53621 | 741 |
In addition, these nameless theorems are registered as safe elimination rules: |
742 |
||
743 |
\begin{indentblock} |
|
744 |
\begin{description} |
|
745 |
||
54386 | 746 |
\item[@{text "t."}\hthm{distinct {\upshape[}THEN notE}@{text ", elim!"}\hthm{\upshape]}\rm:] ~ \\ |
53621 | 747 |
@{thm list.distinct(1)[THEN notE, elim!, no_vars]} \\ |
748 |
@{thm list.distinct(2)[THEN notE, elim!, no_vars]} |
|
749 |
||
750 |
\end{description} |
|
751 |
\end{indentblock} |
|
752 |
||
753 |
\noindent |
|
53543 | 754 |
The next subgroup is concerned with the case combinator: |
755 |
||
53552 | 756 |
\begin{indentblock} |
53543 | 757 |
\begin{description} |
53544 | 758 |
|
53798 | 759 |
\item[@{text "t."}\hthm{case} @{text "[simp, code]"}\rm:] ~ \\ |
53543 | 760 |
@{thm list.case(1)[no_vars]} \\ |
58335
a5a3b576fcfb
generate 'code' attribute only if 'code' plugin is enabled
blanchet
parents:
58311
diff
changeset
|
761 |
@{thm list.case(2)[no_vars]} \\ |
59284 | 762 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
763 |
(Section~\ref{ssec:code-generator}). |
|
53543 | 764 |
|
57542 | 765 |
\item[@{text "t."}\hthm{case_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
53543 | 766 |
@{thm list.case_cong[no_vars]} |
767 |
||
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
768 |
\item[@{text "t."}\hthm{case_cong_weak} @{text "[cong]"}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
769 |
@{thm list.case_cong_weak[no_vars]} |
53543 | 770 |
|
59268 | 771 |
\item[@{text "t."}\hthm{case_distrib}\rm:] ~ \\ |
772 |
@{thm list.case_distrib[no_vars]} |
|
773 |
||
53642 | 774 |
\item[@{text "t."}\hthm{split}\rm:] ~ \\ |
53543 | 775 |
@{thm list.split[no_vars]} |
776 |
||
57542 | 777 |
\item[@{text "t."}\hthm{split_asm}\rm:] ~ \\ |
53543 | 778 |
@{thm list.split_asm[no_vars]} |
779 |
||
53544 | 780 |
\item[@{text "t."}\hthm{splits} = @{text "split split_asm"}] |
53543 | 781 |
|
782 |
\end{description} |
|
53552 | 783 |
\end{indentblock} |
53543 | 784 |
|
785 |
\noindent |
|
54621 | 786 |
The third subgroup revolves around discriminators and selectors: |
53543 | 787 |
|
53552 | 788 |
\begin{indentblock} |
53543 | 789 |
\begin{description} |
53544 | 790 |
|
53694 | 791 |
\item[@{text "t."}\hthm{disc} @{text "[simp]"}\rm:] ~ \\ |
792 |
@{thm list.disc(1)[no_vars]} \\ |
|
793 |
@{thm list.disc(2)[no_vars]} |
|
794 |
||
53703 | 795 |
\item[@{text "t."}\hthm{discI}\rm:] ~ \\ |
796 |
@{thm list.discI(1)[no_vars]} \\ |
|
797 |
@{thm list.discI(2)[no_vars]} |
|
798 |
||
53805 | 799 |
\item[@{text "t."}\hthm{sel} @{text "[simp, code]"}\rm:] ~ \\ |
53694 | 800 |
@{thm list.sel(1)[no_vars]} \\ |
58335
a5a3b576fcfb
generate 'code' attribute only if 'code' plugin is enabled
blanchet
parents:
58311
diff
changeset
|
801 |
@{thm list.sel(2)[no_vars]} \\ |
59284 | 802 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
803 |
(Section~\ref{ssec:code-generator}). |
|
53543 | 804 |
|
53642 | 805 |
\item[@{text "t."}\hthm{collapse} @{text "[simp]"}\rm:] ~ \\ |
53543 | 806 |
@{thm list.collapse(1)[no_vars]} \\ |
58151
414deb2ef328
take out 'x = C' of the simplifier for unit types
blanchet
parents:
58121
diff
changeset
|
807 |
@{thm list.collapse(2)[no_vars]} \\ |
59284 | 808 |
The @{text "[simp]"} attribute is exceptionally omitted for datatypes equipped |
58151
414deb2ef328
take out 'x = C' of the simplifier for unit types
blanchet
parents:
58121
diff
changeset
|
809 |
with a single nullary constructor, because a property of the form |
59284 | 810 |
@{prop "x = C"} is not suitable as a simplification rule. |
53543 | 811 |
|
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
812 |
\item[@{text "t."}\hthm{distinct_disc} @{text "[dest]"}\rm:] ~ \\ |
53543 | 813 |
These properties are missing for @{typ "'a list"} because there is only one |
59284 | 814 |
proper discriminator. If the datatype had been introduced with a second |
53837 | 815 |
discriminator called @{const nonnull}, they would have read thusly: \\[\jot] |
816 |
@{prop "null list \<Longrightarrow> \<not> nonnull list"} \\ |
|
817 |
@{prop "nonnull list \<Longrightarrow> \<not> null list"} |
|
53543 | 818 |
|
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
819 |
\item[@{text "t."}\hthm{exhaust_disc} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
820 |
@{thm list.exhaust_disc[no_vars]} |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
821 |
|
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
822 |
\item[@{text "t."}\hthm{exhaust_sel} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
823 |
@{thm list.exhaust_sel[no_vars]} |
53916 | 824 |
|
53642 | 825 |
\item[@{text "t."}\hthm{expand}\rm:] ~ \\ |
53543 | 826 |
@{thm list.expand[no_vars]} |
827 |
||
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
828 |
\item[@{text "t."}\hthm{split_sel}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
829 |
@{thm list.split_sel[no_vars]} |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
830 |
|
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
831 |
\item[@{text "t."}\hthm{split_sel_asm}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
832 |
@{thm list.split_sel_asm[no_vars]} |
53917 | 833 |
|
57984
cbe9a16f8e11
added collection theorem for consistency and convenience
blanchet
parents:
57983
diff
changeset
|
834 |
\item[@{text "t."}\hthm{split_sels} = @{text "split_sel split_sel_asm"}] |
cbe9a16f8e11
added collection theorem for consistency and convenience
blanchet
parents:
57983
diff
changeset
|
835 |
|
57542 | 836 |
\item[@{text "t."}\hthm{case_eq_if}\rm:] ~ \\ |
54491 | 837 |
@{thm list.case_eq_if[no_vars]} |
53543 | 838 |
|
59273 | 839 |
\item[@{text "t."}\hthm{disc_eq_case}\rm:] ~ \\ |
840 |
@{thm list.disc_eq_case(1)[no_vars]} \\ |
|
841 |
@{thm list.disc_eq_case(2)[no_vars]} |
|
842 |
||
53543 | 843 |
\end{description} |
53552 | 844 |
\end{indentblock} |
54152 | 845 |
|
846 |
\noindent |
|
58151
414deb2ef328
take out 'x = C' of the simplifier for unit types
blanchet
parents:
58121
diff
changeset
|
847 |
In addition, equational versions of @{text t.disc} are registered with the |
59284 | 848 |
@{text "[code]"} attribute. The @{text "[code]"} attribute is set by the |
849 |
@{text code} plugin (Section~\ref{ssec:code-generator}). |
|
62081 | 850 |
\<close> |
851 |
||
852 |
||
853 |
subsubsection \<open> Functorial Theorems |
|
854 |
\label{sssec:functorial-theorems} \<close> |
|
855 |
||
856 |
text \<open> |
|
61349 | 857 |
The functorial theorems are generated for type constructors with at least |
858 |
one live type argument (e.g., @{typ "'a list"}). They are partitioned in two |
|
859 |
subgroups. The first subgroup consists of properties involving the |
|
860 |
constructors or the destructors and either a set function, the map function, |
|
62330 | 861 |
the predicator, or the relator: |
53552 | 862 |
|
863 |
\begin{indentblock} |
|
864 |
\begin{description} |
|
865 |
||
58915 | 866 |
\item[@{text "t."}\hthm{case_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
867 |
@{thm list.case_transfer[no_vars]} \\ |
|
61350 | 868 |
This property is generated by the @{text transfer} plugin |
61349 | 869 |
(Section~\ref{ssec:transfer}). |
61350 | 870 |
%The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
871 |
%(Section~\ref{ssec:transfer}). |
|
58915 | 872 |
|
873 |
\item[@{text "t."}\hthm{sel_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
|
58677 | 874 |
This property is missing for @{typ "'a list"} because there is no common |
58915 | 875 |
selector to all constructors. \\ |
59284 | 876 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
61349 | 877 |
(Section~\ref{ssec:transfer}). |
58915 | 878 |
|
879 |
\item[@{text "t."}\hthm{ctr_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
|
58000 | 880 |
@{thm list.ctr_transfer(1)[no_vars]} \\ |
58915 | 881 |
@{thm list.ctr_transfer(2)[no_vars]} \\ |
59284 | 882 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
61349 | 883 |
(Section~\ref{ssec:transfer}) . |
58915 | 884 |
|
885 |
\item[@{text "t."}\hthm{disc_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
|
58096 | 886 |
@{thm list.disc_transfer(1)[no_vars]} \\ |
58915 | 887 |
@{thm list.disc_transfer(2)[no_vars]} \\ |
59284 | 888 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
61349 | 889 |
(Section~\ref{ssec:transfer}). |
58096 | 890 |
|
53798 | 891 |
\item[@{text "t."}\hthm{set} @{text "[simp, code]"}\rm:] ~ \\ |
53694 | 892 |
@{thm list.set(1)[no_vars]} \\ |
58335
a5a3b576fcfb
generate 'code' attribute only if 'code' plugin is enabled
blanchet
parents:
58311
diff
changeset
|
893 |
@{thm list.set(2)[no_vars]} \\ |
59284 | 894 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
895 |
(Section~\ref{ssec:code-generator}). |
|
53552 | 896 |
|
57988 | 897 |
\item[@{text "t."}\hthm{set_cases} @{text "[consumes 1, cases set: set\<^sub>i_t]"}\rm:] ~ \\ |
57894 | 898 |
@{thm list.set_cases[no_vars]} |
899 |
||
57892 | 900 |
\item[@{text "t."}\hthm{set_intros}\rm:] ~ \\ |
901 |
@{thm list.set_intros(1)[no_vars]} \\ |
|
902 |
@{thm list.set_intros(2)[no_vars]} |
|
903 |
||
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
904 |
\item[@{text "t."}\hthm{set_sel}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
905 |
@{thm list.set_sel[no_vars]} |
57153 | 906 |
|
53798 | 907 |
\item[@{text "t."}\hthm{map} @{text "[simp, code]"}\rm:] ~ \\ |
53552 | 908 |
@{thm list.map(1)[no_vars]} \\ |
58335
a5a3b576fcfb
generate 'code' attribute only if 'code' plugin is enabled
blanchet
parents:
58311
diff
changeset
|
909 |
@{thm list.map(2)[no_vars]} \\ |
59284 | 910 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
911 |
(Section~\ref{ssec:code-generator}). |
|
53552 | 912 |
|
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
913 |
\item[@{text "t."}\hthm{map_disc_iff} @{text "[simp]"}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
914 |
@{thm list.map_disc_iff[no_vars]} |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
915 |
|
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
916 |
\item[@{text "t."}\hthm{map_sel}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
917 |
@{thm list.map_sel[no_vars]} |
57047 | 918 |
|
57542 | 919 |
\item[@{text "t."}\hthm{rel_inject} @{text "[simp]"}\rm:] ~ \\ |
53552 | 920 |
@{thm list.rel_inject(1)[no_vars]} \\ |
921 |
@{thm list.rel_inject(2)[no_vars]} |
|
922 |
||
57542 | 923 |
\item[@{text "t."}\hthm{rel_distinct} @{text "[simp]"}\rm:] ~ \\ |
57526 | 924 |
@{thm list.rel_distinct(1)[no_vars]} \\ |
925 |
@{thm list.rel_distinct(2)[no_vars]} |
|
926 |
||
57542 | 927 |
\item[@{text "t."}\hthm{rel_intros}\rm:] ~ \\ |
57494 | 928 |
@{thm list.rel_intros(1)[no_vars]} \\ |
929 |
@{thm list.rel_intros(2)[no_vars]} |
|
930 |
||
58474 | 931 |
\item[@{text "t."}\hthm{rel_cases} @{text "[consumes 1, case_names t\<^sub>1 \<dots> t\<^sub>m, cases pred]"}\rm:] ~ \\ |
932 |
@{thm list.rel_cases[no_vars]} |
|
53552 | 933 |
|
57564 | 934 |
\item[@{text "t."}\hthm{rel_sel}\rm:] ~ \\ |
935 |
@{thm list.rel_sel[no_vars]} |
|
936 |
||
53552 | 937 |
\end{description} |
938 |
\end{indentblock} |
|
54146 | 939 |
|
940 |
\noindent |
|
941 |
In addition, equational versions of @{text t.rel_inject} and @{text |
|
59284 | 942 |
rel_distinct} are registered with the @{text "[code]"} attribute. The |
943 |
@{text "[code]"} attribute is set by the @{text code} plugin |
|
944 |
(Section~\ref{ssec:code-generator}). |
|
54621 | 945 |
|
946 |
The second subgroup consists of more abstract properties of the set functions, |
|
62330 | 947 |
the map function, the predicator, and the relator: |
54621 | 948 |
|
949 |
\begin{indentblock} |
|
950 |
\begin{description} |
|
951 |
||
57969 | 952 |
\item[@{text "t."}\hthm{inj_map}\rm:] ~ \\ |
953 |
@{thm list.inj_map[no_vars]} |
|
954 |
||
57971 | 955 |
\item[@{text "t."}\hthm{inj_map_strong}\rm:] ~ \\ |
956 |
@{thm list.inj_map_strong[no_vars]} |
|
957 |
||
62330 | 958 |
\item[@{text "t."}\hthm{map_comp}\rm:] ~ \\ |
959 |
@{thm list.map_comp[no_vars]} |
|
58107 | 960 |
|
58245 | 961 |
\item[@{text "t."}\hthm{map_cong0}\rm:] ~ \\ |
54621 | 962 |
@{thm list.map_cong0[no_vars]} |
963 |
||
57542 | 964 |
\item[@{text "t."}\hthm{map_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
54621 | 965 |
@{thm list.map_cong[no_vars]} |
966 |
||
62330 | 967 |
\item[@{text "t."}\hthm{map_cong_pred}\rm:] ~ \\ |
968 |
@{thm list.map_cong_pred[no_vars]} |
|
969 |
||
57982 | 970 |
\item[@{text "t."}\hthm{map_cong_simp}\rm:] ~ \\ |
971 |
@{thm list.map_cong_simp[no_vars]} |
|
972 |
||
59793 | 973 |
\item[@{text "t."}\hthm{map_id0}\rm:] ~ \\ |
974 |
@{thm list.map_id0[no_vars]} |
|
975 |
||
57542 | 976 |
\item[@{text "t."}\hthm{map_id}\rm:] ~ \\ |
54621 | 977 |
@{thm list.map_id[no_vars]} |
978 |
||
57542 | 979 |
\item[@{text "t."}\hthm{map_ident}\rm:] ~ \\ |
56904 | 980 |
@{thm list.map_ident[no_vars]} |
981 |
||
58915 | 982 |
\item[@{text "t."}\hthm{map_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
983 |
@{thm list.map_transfer[no_vars]} \\ |
|
59284 | 984 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
59824 | 985 |
(Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
58103 | 986 |
|
62330 | 987 |
\item[@{text "t."}\hthm{pred_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
988 |
@{thm list.pred_cong[no_vars]} |
|
989 |
||
990 |
\item[@{text "t."}\hthm{pred_cong_simp}\rm:] ~ \\ |
|
991 |
@{thm list.pred_cong_simp[no_vars]} |
|
992 |
||
993 |
\item[@{text "t."}\hthm{pred_map}\rm:] ~ \\ |
|
994 |
@{thm list.pred_map[no_vars]} |
|
995 |
||
996 |
\item[@{text "t."}\hthm{pred_mono_strong}\rm:] ~ \\ |
|
997 |
@{thm list.pred_mono_strong[no_vars]} |
|
998 |
||
999 |
\item[@{text "t."}\hthm{pred_rel}\rm:] ~ \\ |
|
1000 |
@{thm list.pred_rel[no_vars]} |
|
1001 |
||
1002 |
\item[@{text "t."}\hthm{pred_set}\rm:] ~ \\ |
|
1003 |
@{thm list.pred_set[no_vars]} |
|
1004 |
||
1005 |
\item[@{text "t."}\hthm{pred_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
|
1006 |
@{thm list.pred_transfer[no_vars]} \\ |
|
1007 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
|
1008 |
(Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
|
1009 |
||
1010 |
\item[@{text "t."}\hthm{pred_True}\rm:] ~ \\ |
|
1011 |
@{thm list.pred_True[no_vars]} |
|
1012 |
||
1013 |
\item[@{text "t."}\hthm{set_map}\rm:] ~ \\ |
|
1014 |
@{thm list.set_map[no_vars]} |
|
1015 |
||
1016 |
\item[@{text "t."}\hthm{set_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
|
1017 |
@{thm list.set_transfer[no_vars]} \\ |
|
1018 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
|
1019 |
(Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
|
1020 |
||
58244 | 1021 |
\item[@{text "t."}\hthm{rel_compp} @{text "[relator_distr]"}\rm:] ~ \\ |
58245 | 1022 |
@{thm list.rel_compp[no_vars]} \\ |
59284 | 1023 |
The @{text "[relator_distr]"} attribute is set by the @{text lifting} plugin |
1024 |
(Section~\ref{ssec:lifting}). |
|
54621 | 1025 |
|
57542 | 1026 |
\item[@{text "t."}\hthm{rel_conversep}\rm:] ~ \\ |
54621 | 1027 |
@{thm list.rel_conversep[no_vars]} |
1028 |
||
57542 | 1029 |
\item[@{text "t."}\hthm{rel_eq}\rm:] ~ \\ |
54621 | 1030 |
@{thm list.rel_eq[no_vars]} |
1031 |
||
62330 | 1032 |
\item[@{text "t."}\hthm{rel_eq_onp}\rm:] ~ \\ |
1033 |
@{thm list.rel_eq_onp[no_vars]} |
|
1034 |
||
57542 | 1035 |
\item[@{text "t."}\hthm{rel_flip}\rm:] ~ \\ |
54621 | 1036 |
@{thm list.rel_flip[no_vars]} |
1037 |
||
57933 | 1038 |
\item[@{text "t."}\hthm{rel_map}\rm:] ~ \\ |
1039 |
@{thm list.rel_map(1)[no_vars]} \\ |
|
1040 |
@{thm list.rel_map(2)[no_vars]} |
|
1041 |
||
58344 | 1042 |
\item[@{text "t."}\hthm{rel_mono} @{text "[mono, relator_mono]"}\rm:] ~ \\ |
58245 | 1043 |
@{thm list.rel_mono[no_vars]} \\ |
59284 | 1044 |
The @{text "[relator_mono]"} attribute is set by the @{text lifting} plugin |
1045 |
(Section~\ref{ssec:lifting}). |
|
54621 | 1046 |
|
61242 | 1047 |
\item[@{text "t."}\hthm{rel_mono_strong}\rm:] ~ \\ |
1048 |
@{thm list.rel_mono_strong[no_vars]} |
|
1049 |
||
1050 |
\item[@{text "t."}\hthm{rel_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
|
1051 |
@{thm list.rel_cong[no_vars]} |
|
1052 |
||
1053 |
\item[@{text "t."}\hthm{rel_cong_simp}\rm:] ~ \\ |
|
1054 |
@{thm list.rel_cong_simp[no_vars]} |
|
1055 |
||
59793 | 1056 |
\item[@{text "t."}\hthm{rel_refl}\rm:] ~ \\ |
1057 |
@{thm list.rel_refl[no_vars]} |
|
1058 |
||
61240 | 1059 |
\item[@{text "t."}\hthm{rel_refl_strong}\rm:] ~ \\ |
1060 |
@{thm list.rel_refl_strong[no_vars]} |
|
1061 |
||
1062 |
\item[@{text "t."}\hthm{rel_reflp}\rm:] ~ \\ |
|
1063 |
@{thm list.rel_reflp[no_vars]} |
|
1064 |
||
1065 |
\item[@{text "t."}\hthm{rel_symp}\rm:] ~ \\ |
|
1066 |
@{thm list.rel_symp[no_vars]} |
|
1067 |
||
1068 |
\item[@{text "t."}\hthm{rel_transp}\rm:] ~ \\ |
|
1069 |
@{thm list.rel_transp[no_vars]} |
|
1070 |
||
58915 | 1071 |
\item[@{text "t."}\hthm{rel_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1072 |
@{thm list.rel_transfer[no_vars]} \\ |
|
59284 | 1073 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
59824 | 1074 |
(Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
58105 | 1075 |
|
54621 | 1076 |
\end{description} |
1077 |
\end{indentblock} |
|
62081 | 1078 |
\<close> |
1079 |
||
1080 |
||
1081 |
subsubsection \<open> Inductive Theorems |
|
1082 |
\label{sssec:inductive-theorems} \<close> |
|
1083 |
||
1084 |
text \<open> |
|
53623 | 1085 |
The inductive theorems are as follows: |
53544 | 1086 |
|
53552 | 1087 |
\begin{indentblock} |
53544 | 1088 |
\begin{description} |
1089 |
||
57304 | 1090 |
\item[@{text "t."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n, induct t]"}\rm:] ~ \\ |
53544 | 1091 |
@{thm list.induct[no_vars]} |
1092 |
||
57542 | 1093 |
\item[@{text "t."}\hthm{rel_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n, induct pred]"}\rm:] ~ \\ |
57472 | 1094 |
@{thm list.rel_induct[no_vars]} |
1095 |
||
57701 | 1096 |
\item[\begin{tabular}{@ {}l@ {}} |
1097 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm: \\ |
|
1098 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm: \\ |
|
1099 |
\end{tabular}] ~ \\ |
|
57472 | 1100 |
Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
1101 |
prove $m$ properties simultaneously. |
|
1102 |
||
53798 | 1103 |
\item[@{text "t."}\hthm{rec} @{text "[simp, code]"}\rm:] ~ \\ |
53544 | 1104 |
@{thm list.rec(1)[no_vars]} \\ |
58335
a5a3b576fcfb
generate 'code' attribute only if 'code' plugin is enabled
blanchet
parents:
58311
diff
changeset
|
1105 |
@{thm list.rec(2)[no_vars]} \\ |
59284 | 1106 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
1107 |
(Section~\ref{ssec:code-generator}). |
|
53544 | 1108 |
|
58733 | 1109 |
\item[@{text "t."}\hthm{rec_o_map}\rm:] ~ \\ |
1110 |
@{thm list.rec_o_map[no_vars]} |
|
1111 |
||
58915 | 1112 |
\item[@{text "t."}\hthm{rec_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1113 |
@{thm list.rec_transfer[no_vars]} \\ |
|
59284 | 1114 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
59824 | 1115 |
(Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
58447 | 1116 |
|
53544 | 1117 |
\end{description} |
53552 | 1118 |
\end{indentblock} |
53544 | 1119 |
|
1120 |
\noindent |
|
58310 | 1121 |
For convenience, @{command datatype} also provides the following collection: |
53544 | 1122 |
|
53552 | 1123 |
\begin{indentblock} |
53544 | 1124 |
\begin{description} |
1125 |
||
59284 | 1126 |
\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 | 1127 |
@{text t.rel_distinct} @{text t.set} |
53544 | 1128 |
|
1129 |
\end{description} |
|
53552 | 1130 |
\end{indentblock} |
62081 | 1131 |
\<close> |
1132 |
||
1133 |
||
1134 |
subsection \<open> Proof Method |
|
1135 |
\label{ssec:datatype-proof-method} \<close> |
|
1136 |
||
1137 |
subsubsection \<open> \textit{countable_datatype} |
|
1138 |
\label{sssec:datatype-compat} \<close> |
|
1139 |
||
1140 |
text \<open> |
|
1141 |
The theory @{file "~~/src/HOL/Library/Countable.thy"} provides a |
|
1142 |
proof method called @{text countable_datatype} that can be used to prove the |
|
1143 |
countability of many datatypes, building on the countability of the types |
|
1144 |
appearing in their definitions and of any type arguments. For example: |
|
1145 |
\<close> |
|
1146 |
||
1147 |
instance list :: (countable) countable |
|
1148 |
by countable_datatype |
|
1149 |
||
1150 |
||
1151 |
subsection \<open> Compatibility Issues |
|
1152 |
\label{ssec:datatype-compatibility-issues} \<close> |
|
1153 |
||
1154 |
text \<open> |
|
1155 |
The command @{command datatype} has been designed to be highly compatible with |
|
1156 |
the old command, to ease migration. There are nonetheless a few |
|
1157 |
incompatibilities that may arise when porting: |
|
53647 | 1158 |
|
1159 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1160 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1161 |
|
53647 | 1162 |
\item \emph{The Standard ML interfaces are different.} Tools and extensions |
1163 |
written to call the old ML interfaces will need to be adapted to the new |
|
60135
852f7a49ec0c
updated docs, esp. relating to 'datatype_compat'
blanchet
parents:
60134
diff
changeset
|
1164 |
interfaces. The @{text BNF_LFP_Compat} structure provides convenience functions |
852f7a49ec0c
updated docs, esp. relating to 'datatype_compat'
blanchet
parents:
60134
diff
changeset
|
1165 |
that simulate the old interfaces in terms of the new ones. |
54537 | 1166 |
|
1167 |
\item \emph{The recursor @{text rec_t} has a different signature for nested |
|
54185 | 1168 |
recursive datatypes.} In the old package, nested recursion through non-functions |
1169 |
was internally reduced to mutual recursion. This reduction was visible in the |
|
1170 |
type of the recursor, used by \keyw{primrec}. Recursion through functions was |
|
1171 |
handled specially. In the new package, nested recursion (for functions and |
|
1172 |
non-functions) is handled in a more modular fashion. The old-style recursor can |
|
56655 | 1173 |
be generated on demand using @{command primrec} if the recursion is via |
1174 |
new-style datatypes, as explained in |
|
61351 | 1175 |
Section~\ref{sssec:primrec-nested-as-mutual-recursion}, or using |
1176 |
@{command datatype_compat}. |
|
53647 | 1177 |
|
54287 | 1178 |
\item \emph{Accordingly, the induction rule is different for nested recursive |
61351 | 1179 |
datatypes.} Again, the old-style induction rule can be generated on demand |
1180 |
using @{command primrec} if the recursion is via new-style datatypes, as |
|
1181 |
explained in Section~\ref{sssec:primrec-nested-as-mutual-recursion}, or using |
|
1182 |
@{command datatype_compat}. For recursion through functions, the old-style |
|
1183 |
induction rule can be obtained by applying the @{text "[unfolded |
|
1184 |
all_mem_range]"} attribute on @{text t.induct}. |
|
52828 | 1185 |
|
58336 | 1186 |
\item \emph{The @{const size} function has a slightly different definition.} |
1187 |
The new function returns @{text 1} instead of @{text 0} for some nonrecursive |
|
1188 |
constructors. This departure from the old behavior made it possible to implement |
|
62081 | 1189 |
@{const size} in terms of the generic function @{text "t.size_t"}. Moreover, |
1190 |
the new function considers nested occurrences of a value, in the nested |
|
58339 | 1191 |
recursive case. The old behavior can be obtained by disabling the @{text size} |
59282 | 1192 |
plugin (Section~\ref{sec:selecting-plugins}) and instantiating the |
58339 | 1193 |
@{text size} type class manually. |
58336 | 1194 |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
1195 |
\item \emph{The internal constructions are completely different.} Proof texts |
62081 | 1196 |
that unfold the definition of constants introduced by the old command will |
58305
57752a91eec4
renamed 'datatype' to 'old_datatype'; 'datatype' is now alias for 'datatype_new'
blanchet
parents:
58298
diff
changeset
|
1197 |
be difficult to port. |
53647 | 1198 |
|
58207 | 1199 |
\item \emph{Some constants and 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
|
1200 |
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
|
1201 |
the alias @{text t.inducts} for @{text t.induct} is no longer generated. |
53647 | 1202 |
For $m > 1$ mutually recursive datatypes, |
58207 | 1203 |
@{text "rec_t\<^sub>1_\<dots>_t\<^sub>m_i"} has been renamed |
62081 | 1204 |
@{text "rec_t\<^sub>i"} for each @{text "i \<in> {1, \<dots>, m}"}, |
53997 | 1205 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m.inducts(i)"} has been renamed |
62081 | 1206 |
@{text "t\<^sub>i.induct"} for each @{text "i \<in> {1, \<dots>, m}"}, and the |
58207 | 1207 |
collection @{text "t\<^sub>1_\<dots>_t\<^sub>m.size"} (generated by the |
1208 |
@{text size} plugin, Section~\ref{ssec:size}) has been divided into |
|
1209 |
@{text "t\<^sub>1.size"}, \ldots, @{text "t\<^sub>m.size"}. |
|
53647 | 1210 |
|
1211 |
\item \emph{The @{text t.simps} collection has been extended.} |
|
58207 | 1212 |
Previously available theorems are available at the same index as before. |
53647 | 1213 |
|
1214 |
\item \emph{Variables in generated properties have different names.} This is |
|
1215 |
rarely an issue, except in proof texts that refer to variable names in the |
|
1216 |
@{text "[where \<dots>]"} attribute. The solution is to use the more robust |
|
1217 |
@{text "[of \<dots>]"} syntax. |
|
1218 |
\end{itemize} |
|
1219 |
||
62081 | 1220 |
The old command is still available as \keyw{old_datatype} in theory |
1221 |
@{file "~~/src/HOL/Library/Old_Datatype.thy"}. However, there is no general |
|
1222 |
way to register old-style datatypes as new-style datatypes. If the objective |
|
1223 |
is to define new-style datatypes with nested recursion through old-style |
|
1224 |
datatypes, the old-style datatypes can be registered as a BNF |
|
1225 |
(Section~\ref{sec:registering-bounded-natural-functors}). If the objective is |
|
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
1226 |
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
|
1227 |
@{command free_constructors} |
53647 | 1228 |
(Section~\ref{sec:deriving-destructors-and-theorems-for-free-constructors}). |
62081 | 1229 |
\<close> |
1230 |
||
1231 |
||
1232 |
section \<open> Defining Primitively Recursive Functions |
|
1233 |
\label{sec:defining-primitively-recursive-functions} \<close> |
|
1234 |
||
1235 |
text \<open> |
|
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
|
1236 |
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
|
1237 |
command, which supports primitive recursion, or using the more general |
59861 | 1238 |
\keyw{fun}, \keyw{function}, and \keyw{partial_function} commands. In this |
1239 |
tutorial, the focus is on @{command primrec}; \keyw{fun} and \keyw{function} are |
|
1240 |
described in a separate tutorial @{cite "isabelle-function"}. |
|
62081 | 1241 |
\<close> |
1242 |
||
1243 |
||
1244 |
subsection \<open> Introductory Examples |
|
1245 |
\label{ssec:primrec-introductory-examples} \<close> |
|
1246 |
||
1247 |
text \<open> |
|
53646 | 1248 |
Primitive recursion is illustrated through concrete examples based on the |
1249 |
datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More |
|
61304 | 1250 |
examples can be found in the directory @{file "~~/src/HOL/Datatype_Examples"}. |
62081 | 1251 |
\<close> |
1252 |
||
1253 |
||
1254 |
subsubsection \<open> Nonrecursive Types |
|
1255 |
\label{sssec:primrec-nonrecursive-types} \<close> |
|
1256 |
||
1257 |
text \<open> |
|
53621 | 1258 |
Primitive recursion removes one layer of constructors on the left-hand side in |
1259 |
each equation. For example: |
|
62081 | 1260 |
\<close> |
52841 | 1261 |
|
60136 | 1262 |
primrec (nonexhaustive) bool_of_trool :: "trool \<Rightarrow> bool" where |
62081 | 1263 |
"bool_of_trool Faalse \<longleftrightarrow> False" |
1264 |
| "bool_of_trool Truue \<longleftrightarrow> True" |
|
1265 |
||
1266 |
text \<open> \blankline \<close> |
|
52841 | 1267 |
|
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
|
1268 |
primrec the_list :: "'a option \<Rightarrow> 'a list" where |
62081 | 1269 |
"the_list None = []" |
1270 |
| "the_list (Some a) = [a]" |
|
1271 |
||
1272 |
text \<open> \blankline \<close> |
|
53621 | 1273 |
|
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
|
1274 |
primrec the_default :: "'a \<Rightarrow> 'a option \<Rightarrow> 'a" where |
62081 | 1275 |
"the_default d None = d" |
1276 |
| "the_default _ (Some a) = a" |
|
1277 |
||
1278 |
text \<open> \blankline \<close> |
|
53621 | 1279 |
|
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
|
1280 |
primrec mirrror :: "('a, 'b, 'c) triple \<Rightarrow> ('c, 'b, 'a) triple" where |
52841 | 1281 |
"mirrror (Triple a b c) = Triple c b a" |
1282 |
||
62081 | 1283 |
text \<open> |
53621 | 1284 |
\noindent |
1285 |
The equations can be specified in any order, and it is acceptable to leave out |
|
1286 |
some cases, which are then unspecified. Pattern matching on the left-hand side |
|
1287 |
is restricted to a single datatype, which must correspond to the same argument |
|
1288 |
in all equations. |
|
62081 | 1289 |
\<close> |
1290 |
||
1291 |
||
1292 |
subsubsection \<open> Simple Recursion |
|
1293 |
\label{sssec:primrec-simple-recursion} \<close> |
|
1294 |
||
1295 |
text \<open> |
|
53621 | 1296 |
For simple recursive types, recursive calls on a constructor argument are |
1297 |
allowed on the right-hand side: |
|
62081 | 1298 |
\<close> |
52841 | 1299 |
|
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
|
1300 |
primrec replicate :: "nat \<Rightarrow> 'a \<Rightarrow> 'a list" where |
62081 | 1301 |
"replicate Zero _ = []" |
1302 |
| "replicate (Succ n) x = x # replicate n x" |
|
1303 |
||
1304 |
text \<open> \blankline \<close> |
|
52843 | 1305 |
|
60136 | 1306 |
primrec (nonexhaustive) at :: "'a list \<Rightarrow> nat \<Rightarrow> 'a" where |
53644 | 1307 |
"at (x # xs) j = |
52843 | 1308 |
(case j of |
53644 | 1309 |
Zero \<Rightarrow> x |
58245 | 1310 |
| Succ j' \<Rightarrow> at xs j')" |
52843 | 1311 |
|
62081 | 1312 |
text \<open> \blankline \<close> |
53621 | 1313 |
|
59284 | 1314 |
primrec (*<*)(in early) (transfer) (*>*)tfold :: "('a \<Rightarrow> 'b \<Rightarrow> 'b) \<Rightarrow> ('a, 'b) tlist \<Rightarrow> 'b" where |
62081 | 1315 |
"tfold _ (TNil y) = y" |
1316 |
| "tfold f (TCons x xs) = f x (tfold f xs)" |
|
1317 |
||
1318 |
text \<open> |
|
53621 | 1319 |
\noindent |
54402 | 1320 |
Pattern matching is only available for the argument on which the recursion takes |
1321 |
place. Fortunately, it is easy to generate pattern-maching equations using the |
|
62081 | 1322 |
@{command simps_of_case} command provided by the theory |
61304 | 1323 |
@{file "~~/src/HOL/Library/Simps_Case_Conv.thy"}. |
62081 | 1324 |
\<close> |
1325 |
||
1326 |
simps_of_case at_simps_alt: at.simps |
|
1327 |
||
1328 |
text \<open> |
|
1329 |
This generates the lemma collection @{thm [source] at_simps_alt}: |
|
54402 | 1330 |
% |
62081 | 1331 |
\[@{thm at_simps_alt(1)[no_vars]} |
1332 |
\qquad @{thm at_simps_alt(2)[no_vars]}\] |
|
54402 | 1333 |
% |
54184 | 1334 |
The next example is defined using \keyw{fun} to escape the syntactic |
60135
852f7a49ec0c
updated docs, esp. relating to 'datatype_compat'
blanchet
parents:
60134
diff
changeset
|
1335 |
restrictions imposed on primitively recursive functions: |
62081 | 1336 |
\<close> |
52828 | 1337 |
|
53621 | 1338 |
fun at_least_two :: "nat \<Rightarrow> bool" where |
62081 | 1339 |
"at_least_two (Succ (Succ _)) \<longleftrightarrow> True" |
1340 |
| "at_least_two _ \<longleftrightarrow> False" |
|
1341 |
||
1342 |
||
1343 |
subsubsection \<open> Mutual Recursion |
|
1344 |
\label{sssec:primrec-mutual-recursion} \<close> |
|
1345 |
||
1346 |
text \<open> |
|
53621 | 1347 |
The syntax for mutually recursive functions over mutually recursive datatypes |
1348 |
is straightforward: |
|
62081 | 1349 |
\<close> |
52841 | 1350 |
|
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
|
1351 |
primrec |
53623 | 1352 |
nat_of_even_nat :: "even_nat \<Rightarrow> nat" and |
1353 |
nat_of_odd_nat :: "odd_nat \<Rightarrow> nat" |
|
52841 | 1354 |
where |
62081 | 1355 |
"nat_of_even_nat Even_Zero = Zero" |
1356 |
| "nat_of_even_nat (Even_Succ n) = Succ (nat_of_odd_nat n)" |
|
1357 |
| "nat_of_odd_nat (Odd_Succ n) = Succ (nat_of_even_nat n)" |
|
1358 |
||
1359 |
text \<open> \blankline \<close> |
|
53752 | 1360 |
|
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
|
1361 |
primrec |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1362 |
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
|
1363 |
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
|
1364 |
eval\<^sub>f :: "('a \<Rightarrow> int) \<Rightarrow> ('b \<Rightarrow> int) \<Rightarrow> ('a, 'b) fct \<Rightarrow> int" |
52841 | 1365 |
where |
62081 | 1366 |
"eval\<^sub>e \<gamma> \<xi> (Term t) = eval\<^sub>t \<gamma> \<xi> t" |
1367 |
| "eval\<^sub>e \<gamma> \<xi> (Sum t e) = eval\<^sub>t \<gamma> \<xi> t + eval\<^sub>e \<gamma> \<xi> e" |
|
1368 |
| "eval\<^sub>t \<gamma> \<xi> (Factor f) = eval\<^sub>f \<gamma> \<xi> f" |
|
1369 |
| "eval\<^sub>t \<gamma> \<xi> (Prod f t) = eval\<^sub>f \<gamma> \<xi> f + eval\<^sub>t \<gamma> \<xi> t" |
|
1370 |
| "eval\<^sub>f \<gamma> _ (Const a) = \<gamma> a" |
|
1371 |
| "eval\<^sub>f _ \<xi> (Var b) = \<xi> b" |
|
1372 |
| "eval\<^sub>f \<gamma> \<xi> (Expr e) = eval\<^sub>e \<gamma> \<xi> e" |
|
1373 |
||
1374 |
text \<open> |
|
53621 | 1375 |
\noindent |
53647 | 1376 |
Mutual recursion is possible within a single type, using \keyw{fun}: |
62081 | 1377 |
\<close> |
52828 | 1378 |
|
53621 | 1379 |
fun |
1380 |
even :: "nat \<Rightarrow> bool" and |
|
1381 |
odd :: "nat \<Rightarrow> bool" |
|
1382 |
where |
|
62081 | 1383 |
"even Zero = True" |
1384 |
| "even (Succ n) = odd n" |
|
1385 |
| "odd Zero = False" |
|
1386 |
| "odd (Succ n) = even n" |
|
1387 |
||
1388 |
||
1389 |
subsubsection \<open> Nested Recursion |
|
1390 |
\label{sssec:primrec-nested-recursion} \<close> |
|
1391 |
||
1392 |
text \<open> |
|
53621 | 1393 |
In a departure from the old datatype package, nested recursion is normally |
1394 |
handled via the map functions of the nesting type constructors. For example, |
|
1395 |
recursive calls are lifted to lists using @{const map}: |
|
62081 | 1396 |
\<close> |
52828 | 1397 |
|
52843 | 1398 |
(*<*) |
58310 | 1399 |
datatype '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 | 1400 |
(*>*) |
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
|
1401 |
primrec at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" where |
53028 | 1402 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
52843 | 1403 |
(case js of |
1404 |
[] \<Rightarrow> a |
|
53028 | 1405 |
| j # js' \<Rightarrow> at (map (\<lambda>t. at\<^sub>f\<^sub>f t js') ts) j)" |
52843 | 1406 |
|
62081 | 1407 |
text \<open> |
53647 | 1408 |
\noindent |
53621 | 1409 |
The next example features recursion through the @{text option} type. Although |
53623 | 1410 |
@{text option} is not a new-style datatype, it is registered as a BNF with the |
54491 | 1411 |
map function @{const map_option}: |
62081 | 1412 |
\<close> |
52843 | 1413 |
|
61076 | 1414 |
primrec (*<*)(in early) (*>*)sum_btree :: "('a::{zero,plus}) btree \<Rightarrow> 'a" where |
52843 | 1415 |
"sum_btree (BNode a lt rt) = |
54491 | 1416 |
a + the_default 0 (map_option sum_btree lt) + |
1417 |
the_default 0 (map_option sum_btree rt)" |
|
52843 | 1418 |
|
62081 | 1419 |
text \<open> |
53621 | 1420 |
\noindent |
1421 |
The same principle applies for arbitrary type constructors through which |
|
1422 |
recursion is possible. Notably, the map function for the function type |
|
1423 |
(@{text \<Rightarrow>}) is simply composition (@{text "op \<circ>"}): |
|
62081 | 1424 |
\<close> |
52828 | 1425 |
|
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
|
1426 |
primrec (*<*)(in early) (*>*)relabel_ft :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
62081 | 1427 |
"relabel_ft f (FTLeaf x) = FTLeaf (f x)" |
1428 |
| "relabel_ft f (FTNode g) = FTNode (relabel_ft f \<circ> g)" |
|
1429 |
||
1430 |
text \<open> |
|
54182 | 1431 |
\noindent |
62327 | 1432 |
For convenience, the predicator can be used instead of the map function, |
1433 |
typically when defining predicates. For example: |
|
1434 |
\<close> |
|
1435 |
||
1436 |
primrec increasing_tree :: "int \<Rightarrow> int tree\<^sub>f\<^sub>f \<Rightarrow> bool" where |
|
1437 |
"increasing_tree m (Node\<^sub>f\<^sub>f n ts) \<longleftrightarrow> n \<ge> m \<and> pred_list (increasing_tree (n + 1)) ts" |
|
1438 |
||
1439 |
text \<open> |
|
1440 |
\noindent |
|
1441 |
Also for convenience, recursion through functions can also be expressed using |
|
54182 | 1442 |
$\lambda$-abstractions and function application rather than through composition. |
1443 |
For example: |
|
62081 | 1444 |
\<close> |
54182 | 1445 |
|
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
|
1446 |
primrec relabel_ft :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
62081 | 1447 |
"relabel_ft f (FTLeaf x) = FTLeaf (f x)" |
1448 |
| "relabel_ft f (FTNode g) = FTNode (\<lambda>x. relabel_ft f (g x))" |
|
1449 |
||
1450 |
text \<open> \blankline \<close> |
|
54183 | 1451 |
|
60136 | 1452 |
primrec (nonexhaustive) subtree_ft :: "'a \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
54183 | 1453 |
"subtree_ft x (FTNode g) = g x" |
1454 |
||
62081 | 1455 |
text \<open> |
53621 | 1456 |
\noindent |
54182 | 1457 |
For recursion through curried $n$-ary functions, $n$ applications of |
1458 |
@{term "op \<circ>"} are necessary. The examples below illustrate the case where |
|
1459 |
$n = 2$: |
|
62081 | 1460 |
\<close> |
53621 | 1461 |
|
58310 | 1462 |
datatype 'a ftree2 = FTLeaf2 'a | FTNode2 "'a \<Rightarrow> 'a \<Rightarrow> 'a ftree2" |
54182 | 1463 |
|
62081 | 1464 |
text \<open> \blankline \<close> |
54182 | 1465 |
|
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
|
1466 |
primrec (*<*)(in early) (*>*)relabel_ft2 :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree2 \<Rightarrow> 'a ftree2" where |
62081 | 1467 |
"relabel_ft2 f (FTLeaf2 x) = FTLeaf2 (f x)" |
1468 |
| "relabel_ft2 f (FTNode2 g) = FTNode2 (op \<circ> (op \<circ> (relabel_ft2 f)) g)" |
|
1469 |
||
1470 |
text \<open> \blankline \<close> |
|
54182 | 1471 |
|
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
|
1472 |
primrec relabel_ft2 :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree2 \<Rightarrow> 'a ftree2" where |
62081 | 1473 |
"relabel_ft2 f (FTLeaf2 x) = FTLeaf2 (f x)" |
1474 |
| "relabel_ft2 f (FTNode2 g) = FTNode2 (\<lambda>x y. relabel_ft2 f (g x y))" |
|
1475 |
||
1476 |
text \<open> \blankline \<close> |
|
54183 | 1477 |
|
60136 | 1478 |
primrec (nonexhaustive) subtree_ft2 :: "'a \<Rightarrow> 'a \<Rightarrow> 'a ftree2 \<Rightarrow> 'a ftree2" where |
54183 | 1479 |
"subtree_ft2 x y (FTNode2 g) = g x y" |
1480 |
||
53621 | 1481 |
|
62081 | 1482 |
subsubsection \<open> Nested-as-Mutual Recursion |
1483 |
\label{sssec:primrec-nested-as-mutual-recursion} \<close> |
|
53621 | 1484 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1485 |
(*<*) |
59284 | 1486 |
locale n2m |
1487 |
begin |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1488 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1489 |
|
62081 | 1490 |
text \<open> |
53621 | 1491 |
For compatibility with the old package, but also because it is sometimes |
1492 |
convenient in its own right, it is possible to treat nested recursive datatypes |
|
1493 |
as mutually recursive ones if the recursion takes place though new-style |
|
1494 |
datatypes. For example: |
|
62081 | 1495 |
\<close> |
52843 | 1496 |
|
60136 | 1497 |
primrec (nonexhaustive) |
53647 | 1498 |
at\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f \<Rightarrow> nat list \<Rightarrow> 'a" and |
1499 |
ats\<^sub>f\<^sub>f :: "'a tree\<^sub>f\<^sub>f list \<Rightarrow> nat \<Rightarrow> nat list \<Rightarrow> 'a" |
|
52843 | 1500 |
where |
53647 | 1501 |
"at\<^sub>f\<^sub>f (Node\<^sub>f\<^sub>f a ts) js = |
52843 | 1502 |
(case js of |
1503 |
[] \<Rightarrow> a |
|
62081 | 1504 |
| j # js' \<Rightarrow> ats\<^sub>f\<^sub>f ts j js')" |
1505 |
| "ats\<^sub>f\<^sub>f (t # ts) j = |
|
52843 | 1506 |
(case j of |
53647 | 1507 |
Zero \<Rightarrow> at\<^sub>f\<^sub>f t |
58245 | 1508 |
| Succ j' \<Rightarrow> ats\<^sub>f\<^sub>f ts j')" |
52843 | 1509 |
|
62081 | 1510 |
text \<open> |
53647 | 1511 |
\noindent |
54287 | 1512 |
Appropriate induction rules are generated as |
54031 | 1513 |
@{thm [source] at\<^sub>f\<^sub>f.induct}, |
1514 |
@{thm [source] ats\<^sub>f\<^sub>f.induct}, and |
|
54287 | 1515 |
@{thm [source] at\<^sub>f\<^sub>f_ats\<^sub>f\<^sub>f.induct}. The |
1516 |
induction rules and the underlying recursors are generated on a per-need basis |
|
1517 |
and are kept in a cache to speed up subsequent definitions. |
|
53647 | 1518 |
|
1519 |
Here is a second example: |
|
62081 | 1520 |
\<close> |
53621 | 1521 |
|
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
|
1522 |
primrec |
61076 | 1523 |
sum_btree :: "('a::{zero,plus}) btree \<Rightarrow> 'a" and |
53330
77da8d3c46e0
fixed docs w.r.t. availability of "primrec_new" and friends
blanchet
parents:
53262
diff
changeset
|
1524 |
sum_btree_option :: "'a btree option \<Rightarrow> 'a" |
52843 | 1525 |
where |
1526 |
"sum_btree (BNode a lt rt) = |
|
62081 | 1527 |
a + sum_btree_option lt + sum_btree_option rt" |
1528 |
| "sum_btree_option None = 0" |
|
1529 |
| "sum_btree_option (Some t) = sum_btree t" |
|
1530 |
||
1531 |
text \<open> |
|
53621 | 1532 |
% * can pretend a nested type is mutually recursive (if purely inductive) |
1533 |
% * avoids the higher-order map |
|
1534 |
% * e.g. |
|
1535 |
||
53617 | 1536 |
% * this can always be avoided; |
1537 |
% * e.g. in our previous example, we first mapped the recursive |
|
1538 |
% calls, then we used a generic at function to retrieve the result |
|
1539 |
% |
|
1540 |
% * there's no hard-and-fast rule of when to use one or the other, |
|
1541 |
% 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
|
1542 |
% primrec |
53617 | 1543 |
% |
1544 |
% * higher-order approach, considering nesting as nesting, is more |
|
1545 |
% compositional -- e.g. we saw how we could reuse an existing polymorphic |
|
53647 | 1546 |
% at or the_default, whereas @{const ats\<^sub>f\<^sub>f} is much more specific |
53617 | 1547 |
% |
1548 |
% * but: |
|
1549 |
% * is perhaps less intuitive, because it requires higher-order thinking |
|
1550 |
% * may seem inefficient, and indeed with the code generator the |
|
1551 |
% mutually recursive version might be nicer |
|
1552 |
% * is somewhat indirect -- must apply a map first, then compute a result |
|
1553 |
% (cannot mix) |
|
53647 | 1554 |
% * the auxiliary functions like @{const ats\<^sub>f\<^sub>f} are sometimes useful in own right |
53617 | 1555 |
% |
1556 |
% * impact on automation unclear |
|
1557 |
% |
|
62081 | 1558 |
\<close> |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1559 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1560 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1561 |
(*>*) |
52843 | 1562 |
|
52824 | 1563 |
|
62081 | 1564 |
subsection \<open> Command Syntax |
1565 |
\label{ssec:primrec-command-syntax} \<close> |
|
1566 |
||
1567 |
subsubsection \<open> \keyw{primrec} |
|
1568 |
\label{sssec:primrec-new} \<close> |
|
1569 |
||
1570 |
text \<open> |
|
53829 | 1571 |
\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
|
1572 |
@{command_def "primrec"} & : & @{text "local_theory \<rightarrow> local_theory"} |
53829 | 1573 |
\end{matharray} |
52794 | 1574 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1575 |
@{rail \<open> |
59277 | 1576 |
@@{command primrec} target? @{syntax pr_options}? fixes \<newline> |
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1577 |
@'where' (@{syntax pr_equation} + '|') |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1578 |
; |
59282 | 1579 |
@{syntax_def pr_options}: '(' ((@{syntax plugins} | 'nonexhaustive' | 'transfer') + ',') ')' |
52840 | 1580 |
; |
53829 | 1581 |
@{syntax_def pr_equation}: thmdecl? prop |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1582 |
\<close>} |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1583 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1584 |
\medskip |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1585 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1586 |
\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
|
1587 |
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
|
1588 |
over datatypes. |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1589 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1590 |
The syntactic entity \synt{target} can be used to specify a local context, |
55474 | 1591 |
\synt{fixes} denotes a list of names with optional type signatures, |
1592 |
\synt{thmdecl} denotes an optional name for the formula that follows, and |
|
58620 | 1593 |
\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
|
1594 |
|
59280 | 1595 |
The optional target is optionally followed by a combination of the following |
1596 |
options: |
|
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1597 |
|
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1598 |
\begin{itemize} |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1599 |
\setlength{\itemsep}{0pt} |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1600 |
|
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1601 |
\item |
59282 | 1602 |
The @{text plugins} option indicates which plugins should be enabled |
1603 |
(@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
|
1604 |
||
1605 |
\item |
|
1606 |
The @{text nonexhaustive} option indicates that the functions are not |
|
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1607 |
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
|
1608 |
warning that is normally emitted when some constructors are missing. |
59277 | 1609 |
|
1610 |
\item |
|
59282 | 1611 |
The @{text transfer} option indicates that an unconditional transfer rule |
59278 | 1612 |
should be generated and proved @{text "by transfer_prover"}. The |
1613 |
@{text "[transfer_rule]"} attribute is set on the generated theorem. |
|
56123
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1614 |
\end{itemize} |
a27859b0ef7d
document the new 'nonexhaustive' option (cf. 52e8f110fec3)
blanchet
parents:
55945
diff
changeset
|
1615 |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1616 |
%%% TODO: elaborate on format of the equations |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
1617 |
%%% TODO: elaborate on mutual and nested-to-mutual |
62081 | 1618 |
\<close> |
1619 |
||
1620 |
||
1621 |
subsection \<open> Generated Theorems |
|
1622 |
\label{ssec:primrec-generated-theorems} \<close> |
|
52824 | 1623 |
|
59284 | 1624 |
(*<*) |
1625 |
context early |
|
1626 |
begin |
|
1627 |
(*>*) |
|
1628 |
||
62081 | 1629 |
text \<open> |
59284 | 1630 |
The @{command primrec} command generates the following properties (listed |
1631 |
for @{const tfold}): |
|
1632 |
||
1633 |
\begin{indentblock} |
|
1634 |
\begin{description} |
|
1635 |
||
1636 |
\item[@{text "f."}\hthm{simps} @{text "[simp, code]"}\rm:] ~ \\ |
|
1637 |
@{thm tfold.simps(1)[no_vars]} \\ |
|
1638 |
@{thm tfold.simps(2)[no_vars]} \\ |
|
1639 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
|
1640 |
(Section~\ref{ssec:code-generator}). |
|
1641 |
||
1642 |
\item[@{text "f."}\hthm{transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
|
1643 |
@{thm tfold.transfer[no_vars]} \\ |
|
1644 |
This theorem is generated by the @{text transfer} plugin |
|
1645 |
(Section~\ref{ssec:transfer}) for functions declared with the @{text transfer} |
|
1646 |
option enabled. |
|
1647 |
||
1648 |
\item[@{text "f."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
|
1649 |
This induction rule is generated for nested-as-mutual recursive functions |
|
1650 |
(Section~\ref{sssec:primrec-nested-as-mutual-recursion}). |
|
1651 |
||
1652 |
\item[@{text "f\<^sub>1_\<dots>_f\<^sub>m."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
|
1653 |
This induction rule is generated for nested-as-mutual recursive functions |
|
1654 |
(Section~\ref{sssec:primrec-nested-as-mutual-recursion}). Given $m > 1$ mutually |
|
1655 |
recursive functions, this rule can be used to prove $m$ properties |
|
1656 |
simultaneously. |
|
1657 |
||
1658 |
\end{description} |
|
1659 |
\end{indentblock} |
|
62081 | 1660 |
\<close> |
59284 | 1661 |
|
1662 |
(*<*) |
|
1663 |
end |
|
1664 |
(*>*) |
|
53619 | 1665 |
|
52824 | 1666 |
|
62081 | 1667 |
subsection \<open> Recursive Default Values for Selectors |
1668 |
\label{ssec:primrec-recursive-default-values-for-selectors} \<close> |
|
1669 |
||
1670 |
text \<open> |
|
52827 | 1671 |
A datatype selector @{text un_D} can have a default value for each constructor |
1672 |
on which it is not otherwise specified. Occasionally, it is useful to have the |
|
55354 | 1673 |
default value be defined recursively. This leads to a chicken-and-egg |
1674 |
situation, because the datatype is not introduced yet at the moment when the |
|
1675 |
selectors are introduced. Of course, we can always define the selectors |
|
1676 |
manually afterward, but we then have to state and prove all the characteristic |
|
1677 |
theorems ourselves instead of letting the package do it. |
|
1678 |
||
1679 |
Fortunately, there is a workaround that relies on overloading to relieve us |
|
1680 |
from the tedium of manual derivations: |
|
52827 | 1681 |
|
1682 |
\begin{enumerate} |
|
1683 |
\setlength{\itemsep}{0pt} |
|
1684 |
||
1685 |
\item |
|
61076 | 1686 |
Introduce a fully unspecified constant @{text "un_D\<^sub>0 :: 'a"} using |
58931 | 1687 |
@{command consts}. |
52827 | 1688 |
|
1689 |
\item |
|
53535 | 1690 |
Define the datatype, specifying @{text "un_D\<^sub>0"} as the selector's default |
1691 |
value. |
|
52827 | 1692 |
|
1693 |
\item |
|
53535 | 1694 |
Define the behavior of @{text "un_D\<^sub>0"} on values of the newly introduced |
1695 |
datatype using the \keyw{overloading} command. |
|
52827 | 1696 |
|
1697 |
\item |
|
1698 |
Derive the desired equation on @{text un_D} from the characteristic equations |
|
1699 |
for @{text "un_D\<^sub>0"}. |
|
1700 |
\end{enumerate} |
|
1701 |
||
53619 | 1702 |
\noindent |
52827 | 1703 |
The following example illustrates this procedure: |
62081 | 1704 |
\<close> |
52827 | 1705 |
|
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1706 |
(*<*) |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1707 |
hide_const termi |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1708 |
(*>*) |
52827 | 1709 |
consts termi\<^sub>0 :: 'a |
1710 |
||
62081 | 1711 |
text \<open> \blankline \<close> |
53619 | 1712 |
|
58310 | 1713 |
datatype ('a, 'b) tlist = |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1714 |
TNil (termi: 'b) |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1715 |
| TCons (thd: 'a) (ttl: "('a, 'b) tlist") |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1716 |
where |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1717 |
"ttl (TNil y) = TNil y" |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1718 |
| "termi (TCons _ xs) = termi\<^sub>0 xs" |
52827 | 1719 |
|
62081 | 1720 |
text \<open> \blankline \<close> |
53619 | 1721 |
|
52827 | 1722 |
overloading |
61076 | 1723 |
termi\<^sub>0 \<equiv> "termi\<^sub>0 :: ('a, 'b) tlist \<Rightarrow> 'b" |
52827 | 1724 |
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
|
1725 |
primrec termi\<^sub>0 :: "('a, 'b) tlist \<Rightarrow> 'b" where |
62081 | 1726 |
"termi\<^sub>0 (TNil y) = y" |
1727 |
| "termi\<^sub>0 (TCons x xs) = termi\<^sub>0 xs" |
|
52827 | 1728 |
end |
1729 |
||
62081 | 1730 |
text \<open> \blankline \<close> |
53619 | 1731 |
|
55354 | 1732 |
lemma termi_TCons[simp]: "termi (TCons x xs) = termi xs" |
60152 | 1733 |
by (cases xs) auto |
52827 | 1734 |
|
1735 |
||
62081 | 1736 |
subsection \<open> Compatibility Issues |
1737 |
\label{ssec:primrec-compatibility-issues} \<close> |
|
1738 |
||
1739 |
text \<open> |
|
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
|
1740 |
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
|
1741 |
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
|
1742 |
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
|
1743 |
porting to the new package: |
53997 | 1744 |
|
1745 |
\begin{itemize} |
|
1746 |
\setlength{\itemsep}{0pt} |
|
1747 |
||
54185 | 1748 |
\item \emph{Some theorems have different names.} |
53997 | 1749 |
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
|
1750 |
@{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
|
1751 |
subcollections @{text "f\<^sub>i.simps"}. |
53997 | 1752 |
\end{itemize} |
62081 | 1753 |
\<close> |
1754 |
||
1755 |
||
1756 |
section \<open> Defining Codatatypes |
|
1757 |
\label{sec:defining-codatatypes} \<close> |
|
1758 |
||
1759 |
text \<open> |
|
53829 | 1760 |
Codatatypes can be specified using the @{command codatatype} command. The |
53623 | 1761 |
command is first illustrated through concrete examples featuring different |
1762 |
flavors of corecursion. More examples can be found in the directory |
|
61304 | 1763 |
@{file "~~/src/HOL/Datatype_Examples"}. The \emph{Archive of Formal Proofs} also |
1764 |
includes some useful codatatypes, notably for lazy lists @{cite |
|
1765 |
"lochbihler-2010"}. |
|
62081 | 1766 |
\<close> |
1767 |
||
1768 |
||
1769 |
subsection \<open> Introductory Examples |
|
1770 |
\label{ssec:codatatype-introductory-examples} \<close> |
|
1771 |
||
1772 |
subsubsection \<open> Simple Corecursion |
|
1773 |
\label{sssec:codatatype-simple-corecursion} \<close> |
|
1774 |
||
1775 |
text \<open> |
|
57542 | 1776 |
Non-corecursive codatatypes coincide with the corresponding datatypes, so they |
56947 | 1777 |
are rarely used in practice. \emph{Corecursive codatatypes} have the same syntax |
53623 | 1778 |
as recursive datatypes, except for the command name. For example, here is the |
1779 |
definition of lazy lists: |
|
62081 | 1780 |
\<close> |
53623 | 1781 |
|
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1782 |
codatatype (lset: 'a) llist = |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1783 |
lnull: LNil |
53623 | 1784 |
| LCons (lhd: 'a) (ltl: "'a llist") |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1785 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1786 |
map: lmap |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1787 |
rel: llist_all2 |
62330 | 1788 |
pred: llist_all |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1789 |
where |
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
1790 |
"ltl LNil = LNil" |
53623 | 1791 |
|
62081 | 1792 |
text \<open> |
53623 | 1793 |
\noindent |
1794 |
Lazy lists can be infinite, such as @{text "LCons 0 (LCons 0 (\<dots>))"} and |
|
53647 | 1795 |
@{text "LCons 0 (LCons 1 (LCons 2 (\<dots>)))"}. Here is a related type, that of |
1796 |
infinite streams: |
|
62081 | 1797 |
\<close> |
53647 | 1798 |
|
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1799 |
codatatype (sset: 'a) stream = |
53647 | 1800 |
SCons (shd: 'a) (stl: "'a stream") |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1801 |
for |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1802 |
map: smap |
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
1803 |
rel: stream_all2 |
53647 | 1804 |
|
62081 | 1805 |
text \<open> |
53647 | 1806 |
\noindent |
1807 |
Another interesting type that can |
|
53623 | 1808 |
be defined as a codatatype is that of the extended natural numbers: |
62081 | 1809 |
\<close> |
53623 | 1810 |
|
58245 | 1811 |
codatatype enat = EZero | ESucc enat |
53623 | 1812 |
|
62081 | 1813 |
text \<open> |
53623 | 1814 |
\noindent |
58245 | 1815 |
This type has exactly one infinite element, @{text "ESucc (ESucc (ESucc (\<dots>)))"}, |
53623 | 1816 |
that represents $\infty$. In addition, it has finite values of the form |
58245 | 1817 |
@{text "ESucc (\<dots> (ESucc EZero)\<dots>)"}. |
53675 | 1818 |
|
1819 |
Here is an example with many constructors: |
|
62081 | 1820 |
\<close> |
53623 | 1821 |
|
53675 | 1822 |
codatatype 'a process = |
1823 |
Fail |
|
1824 |
| Skip (cont: "'a process") |
|
1825 |
| Action (prefix: 'a) (cont: "'a process") |
|
1826 |
| Choice (left: "'a process") (right: "'a process") |
|
1827 |
||
62081 | 1828 |
text \<open> |
53829 | 1829 |
\noindent |
53750 | 1830 |
Notice that the @{const cont} selector is associated with both @{const Skip} |
54146 | 1831 |
and @{const Action}. |
62081 | 1832 |
\<close> |
1833 |
||
1834 |
||
1835 |
subsubsection \<open> Mutual Corecursion |
|
1836 |
\label{sssec:codatatype-mutual-corecursion} \<close> |
|
1837 |
||
1838 |
text \<open> |
|
53623 | 1839 |
\noindent |
1840 |
The example below introduces a pair of \emph{mutually corecursive} types: |
|
62081 | 1841 |
\<close> |
53623 | 1842 |
|
58245 | 1843 |
codatatype even_enat = Even_EZero | Even_ESucc odd_enat |
1844 |
and odd_enat = Odd_ESucc even_enat |
|
53623 | 1845 |
|
1846 |
||
62081 | 1847 |
subsubsection \<open> Nested Corecursion |
1848 |
\label{sssec:codatatype-nested-corecursion} \<close> |
|
1849 |
||
1850 |
text \<open> |
|
53623 | 1851 |
\noindent |
53675 | 1852 |
The next examples feature \emph{nested corecursion}: |
62081 | 1853 |
\<close> |
53623 | 1854 |
|
53644 | 1855 |
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 | 1856 |
|
62081 | 1857 |
text \<open> \blankline \<close> |
53752 | 1858 |
|
53644 | 1859 |
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 | 1860 |
|
62081 | 1861 |
text \<open> \blankline \<close> |
53752 | 1862 |
|
55350 | 1863 |
codatatype 'a sm = SM (accept: bool) (trans: "'a \<Rightarrow> 'a sm") |
53675 | 1864 |
|
52824 | 1865 |
|
62081 | 1866 |
subsection \<open> Command Syntax |
1867 |
\label{ssec:codatatype-command-syntax} \<close> |
|
1868 |
||
1869 |
subsubsection \<open> \keyw{codatatype} |
|
1870 |
\label{sssec:codatatype} \<close> |
|
1871 |
||
1872 |
text \<open> |
|
53829 | 1873 |
\begin{matharray}{rcl} |
1874 |
@{command_def "codatatype"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
1875 |
\end{matharray} |
|
1876 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1877 |
@{rail \<open> |
59282 | 1878 |
@@{command codatatype} target? @{syntax dt_options}? @{syntax dt_spec} |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
1879 |
\<close>} |
53829 | 1880 |
|
55351 | 1881 |
\medskip |
1882 |
||
53829 | 1883 |
\noindent |
52827 | 1884 |
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
|
1885 |
(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
|
1886 |
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
|
1887 |
codatatypes. |
62081 | 1888 |
\<close> |
1889 |
||
1890 |
||
1891 |
subsection \<open> Generated Constants |
|
1892 |
\label{ssec:codatatype-generated-constants} \<close> |
|
1893 |
||
1894 |
text \<open> |
|
53623 | 1895 |
Given a codatatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
1896 |
with $m > 0$ live type variables and $n$ constructors @{text "t.C\<^sub>1"}, |
|
1897 |
\ldots, @{text "t.C\<^sub>n"}, the same auxiliary constants are generated as for |
|
1898 |
datatypes (Section~\ref{ssec:datatype-generated-constants}), except that the |
|
58190 | 1899 |
recursor is replaced by a dual concept: |
53623 | 1900 |
|
55354 | 1901 |
\medskip |
1902 |
||
1903 |
\begin{tabular}{@ {}ll@ {}} |
|
1904 |
Corecursor: & |
|
56655 | 1905 |
@{text t.corec_t} |
55354 | 1906 |
\end{tabular} |
62081 | 1907 |
\<close> |
1908 |
||
1909 |
||
1910 |
subsection \<open> Generated Theorems |
|
1911 |
\label{ssec:codatatype-generated-theorems} \<close> |
|
1912 |
||
1913 |
text \<open> |
|
53829 | 1914 |
The characteristic theorems generated by @{command codatatype} are grouped in |
53623 | 1915 |
three broad categories: |
1916 |
||
1917 |
\begin{itemize} |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1918 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
1919 |
|
56655 | 1920 |
\item The \emph{free constructor theorems} |
1921 |
(Section~\ref{sssec:free-constructor-theorems}) are properties of the |
|
1922 |
constructors and destructors that can be derived for any freely generated type. |
|
1923 |
||
1924 |
\item The \emph{functorial theorems} |
|
1925 |
(Section~\ref{sssec:functorial-theorems}) are properties of datatypes related to |
|
53623 | 1926 |
their BNF nature. |
1927 |
||
56655 | 1928 |
\item The \emph{coinductive theorems} (Section~\ref{sssec:coinductive-theorems}) |
1929 |
are properties of datatypes related to their coinductive nature. |
|
53623 | 1930 |
\end{itemize} |
1931 |
||
1932 |
\noindent |
|
56655 | 1933 |
The first two categories are exactly as for datatypes. |
62081 | 1934 |
\<close> |
1935 |
||
1936 |
||
1937 |
subsubsection \<open> Coinductive Theorems |
|
1938 |
\label{sssec:coinductive-theorems} \<close> |
|
1939 |
||
1940 |
text \<open> |
|
54031 | 1941 |
The coinductive theorems are listed below for @{typ "'a llist"}: |
53623 | 1942 |
|
1943 |
\begin{indentblock} |
|
1944 |
\begin{description} |
|
1945 |
||
53643 | 1946 |
\item[\begin{tabular}{@ {}l@ {}} |
57304 | 1947 |
@{text "t."}\hthm{coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1948 |
\phantom{@{text "t."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
1949 |
D\<^sub>n, coinduct t]"}\rm: |
|
53643 | 1950 |
\end{tabular}] ~ \\ |
53623 | 1951 |
@{thm llist.coinduct[no_vars]} |
53617 | 1952 |
|
53643 | 1953 |
\item[\begin{tabular}{@ {}l@ {}} |
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1954 |
@{text "t."}\hthm{coinduct_strong} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1955 |
\phantom{@{text "t."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
53643 | 1956 |
\end{tabular}] ~ \\ |
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1957 |
@{thm llist.coinduct_strong[no_vars]} |
53617 | 1958 |
|
53643 | 1959 |
\item[\begin{tabular}{@ {}l@ {}} |
57304 | 1960 |
@{text "t."}\hthm{rel_coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1961 |
\phantom{@{text "t."}\hthm{rel_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
1962 |
D\<^sub>n, coinduct pred]"}\rm: |
|
1963 |
\end{tabular}] ~ \\ |
|
1964 |
@{thm llist.rel_coinduct[no_vars]} |
|
1965 |
||
1966 |
\item[\begin{tabular}{@ {}l@ {}} |
|
53643 | 1967 |
@{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]"} \\ |
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1968 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{coinduct_strong} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1969 |
\phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: \\ |
57542 | 1970 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1971 |
\phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: \\ |
|
53643 | 1972 |
\end{tabular}] ~ \\ |
1973 |
Given $m > 1$ mutually corecursive codatatypes, these coinduction rules can be |
|
1974 |
used to prove $m$ properties simultaneously. |
|
1975 |
||
57701 | 1976 |
\item[\begin{tabular}{@ {}l@ {}} |
1977 |
@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{set_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n,"} \\ |
|
1978 |
\phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{set_induct} @{text "["}}@{text "induct set: set\<^sub>j_t\<^sub>1, \<dots>, induct set: set\<^sub>j_t\<^sub>m]"}\rm: \\ |
|
1979 |
\end{tabular}] ~ \\ |
|
1980 |
@{thm llist.set_induct[no_vars]} \\ |
|
1981 |
If $m = 1$, the attribute @{text "[consumes 1]"} is generated as well. |
|
1982 |
||
54031 | 1983 |
\item[@{text "t."}\hthm{corec}\rm:] ~ \\ |
53623 | 1984 |
@{thm llist.corec(1)[no_vars]} \\ |
1985 |
@{thm llist.corec(2)[no_vars]} |
|
1986 |
||
57542 | 1987 |
\item[@{text "t."}\hthm{corec_code} @{text "[code]"}\rm:] ~ \\ |
58335
a5a3b576fcfb
generate 'code' attribute only if 'code' plugin is enabled
blanchet
parents:
58311
diff
changeset
|
1988 |
@{thm llist.corec_code[no_vars]} \\ |
59284 | 1989 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
1990 |
(Section~\ref{ssec:code-generator}). |
|
57490 | 1991 |
|
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1992 |
\item[@{text "t."}\hthm{corec_disc}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1993 |
@{thm llist.corec_disc(1)[no_vars]} \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1994 |
@{thm llist.corec_disc(2)[no_vars]} |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1995 |
|
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1996 |
\item[@{text "t."}\hthm{corec_disc_iff} @{text "[simp]"}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1997 |
@{thm llist.corec_disc_iff(1)[no_vars]} \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1998 |
@{thm llist.corec_disc_iff(2)[no_vars]} |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
1999 |
|
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
2000 |
\item[@{text "t."}\hthm{corec_sel} @{text "[simp]"}\rm:] ~ \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
2001 |
@{thm llist.corec_sel(1)[no_vars]} \\ |
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
2002 |
@{thm llist.corec_sel(2)[no_vars]} |
53643 | 2003 |
|
58735 | 2004 |
\item[@{text "t."}\hthm{map_o_corec}\rm:] ~ \\ |
2005 |
@{thm llist.map_o_corec[no_vars]} |
|
2006 |
||
58915 | 2007 |
\item[@{text "t."}\hthm{corec_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
2008 |
@{thm llist.corec_transfer[no_vars]} \\ |
|
59284 | 2009 |
The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
59824 | 2010 |
(Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
58449 | 2011 |
|
53623 | 2012 |
\end{description} |
2013 |
\end{indentblock} |
|
2014 |
||
2015 |
\noindent |
|
53829 | 2016 |
For convenience, @{command codatatype} also provides the following collection: |
53623 | 2017 |
|
2018 |
\begin{indentblock} |
|
2019 |
\begin{description} |
|
2020 |
||
59284 | 2021 |
\item[@{text "t."}\hthm{simps}] = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.corec_disc_iff} @{text t.corec_sel} \\ |
55896 | 2022 |
@{text t.map} @{text t.rel_inject} @{text t.rel_distinct} @{text t.set} |
53623 | 2023 |
|
2024 |
\end{description} |
|
2025 |
\end{indentblock} |
|
62081 | 2026 |
\<close> |
2027 |
||
2028 |
||
2029 |
section \<open> Defining Primitively Corecursive Functions |
|
2030 |
\label{sec:defining-primitively-corecursive-functions} \<close> |
|
2031 |
||
2032 |
text \<open> |
|
54183 | 2033 |
Corecursive functions can be specified using the @{command primcorec} and |
61788 | 2034 |
\keyw{prim\-corec\-ursive} commands, which support primitive corecursion. |
2035 |
Other approaches include the more general \keyw{partial_function} command, the |
|
2036 |
forthcoming \keyw{corec} command @{cite "blanchette-et-al-2015-corec"}, and |
|
2037 |
techniques based on domains and topologies @{cite "lochbihler-hoelzl-2014"}. |
|
2038 |
In this tutorial, the focus is on @{command primcorec} and |
|
2039 |
@{command primcorecursive}. More examples can be found in the directory |
|
61304 | 2040 |
@{file "~~/src/HOL/Datatype_Examples"}. |
53644 | 2041 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2042 |
Whereas recursive functions consume datatypes one constructor at a time, |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2043 |
corecursive functions construct codatatypes one constructor at a time. |
53752 | 2044 |
Partly reflecting a lack of agreement among proponents of coalgebraic methods, |
2045 |
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
|
2046 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2047 |
\begin{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2048 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2049 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2050 |
\abovedisplayskip=.5\abovedisplayskip |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2051 |
\belowdisplayskip=.5\belowdisplayskip |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2052 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2053 |
\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
|
2054 |
\[@{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
|
2055 |
equations of the form |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2056 |
\[@{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
|
2057 |
This style is popular in the coalgebraic literature. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2058 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2059 |
\item The \emph{constructor view} specifies $f$ by equations of the form |
54183 | 2060 |
\[@{text "\<dots> \<Longrightarrow> f x\<^sub>1 \<dots> x\<^sub>n = C\<^sub>j \<dots>"}\] |
53752 | 2061 |
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
|
2062 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2063 |
\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
|
2064 |
\[@{text "f x\<^sub>1 \<dots> x\<^sub>n = \<dots>"}\] |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2065 |
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
|
2066 |
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
|
2067 |
style. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2068 |
\end{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2069 |
|
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
|
2070 |
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
|
2071 |
characteristic theorems for all three styles are generated. |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2072 |
|
52828 | 2073 |
%%% TODO: partial_function? E.g. for defining tail recursive function on lazy |
2074 |
%%% lists (cf. terminal0 in TLList.thy) |
|
62081 | 2075 |
\<close> |
2076 |
||
2077 |
||
2078 |
subsection \<open> Introductory Examples |
|
2079 |
\label{ssec:primcorec-introductory-examples} \<close> |
|
2080 |
||
2081 |
text \<open> |
|
53646 | 2082 |
Primitive corecursion is illustrated through concrete examples based on the |
2083 |
codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More |
|
61304 | 2084 |
examples can be found in the directory @{file "~~/src/HOL/Datatype_Examples"}. |
2085 |
The code view is favored in the examples below. Sections |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2086 |
\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
|
2087 |
present the same examples expressed using the constructor and destructor views. |
62081 | 2088 |
\<close> |
2089 |
||
2090 |
||
2091 |
subsubsection \<open> Simple Corecursion |
|
2092 |
\label{sssec:primcorec-simple-corecursion} \<close> |
|
2093 |
||
2094 |
text \<open> |
|
53752 | 2095 |
Following the code view, corecursive calls are allowed on the right-hand side as |
2096 |
long as they occur under a constructor, which itself appears either directly to |
|
2097 |
the right of the equal sign or in a conditional expression: |
|
62081 | 2098 |
\<close> |
53646 | 2099 |
|
59284 | 2100 |
primcorec (*<*)(transfer) (*>*)literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
54072 | 2101 |
"literate g x = LCons x (literate g (g x))" |
53647 | 2102 |
|
62081 | 2103 |
text \<open> \blankline \<close> |
53677 | 2104 |
|
53826 | 2105 |
primcorec siterate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a stream" where |
54072 | 2106 |
"siterate g x = SCons x (siterate g (g x))" |
53644 | 2107 |
|
62081 | 2108 |
text \<open> |
53646 | 2109 |
\noindent |
2110 |
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
|
2111 |
\emph{productive}. The above functions compute the infinite lazy list or stream |
54072 | 2112 |
@{text "[x, g x, g (g x), \<dots>]"}. Productivity guarantees that prefixes |
2113 |
@{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
|
2114 |
@{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
|
2115 |
times. |
53646 | 2116 |
|
53752 | 2117 |
Corecursive functions construct codatatype values, but nothing prevents them |
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
2118 |
from also consuming such values. The following function drops every second |
53675 | 2119 |
element in a stream: |
62081 | 2120 |
\<close> |
53675 | 2121 |
|
53826 | 2122 |
primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
53675 | 2123 |
"every_snd s = SCons (shd s) (stl (stl s))" |
2124 |
||
62081 | 2125 |
text \<open> |
53752 | 2126 |
\noindent |
56124 | 2127 |
Constructs such as @{text "let"}--@{text "in"}, @{text |
2128 |
"if"}--@{text "then"}--@{text "else"}, and @{text "case"}--@{text "of"} may |
|
53646 | 2129 |
appear around constructors that guard corecursive calls: |
62081 | 2130 |
\<close> |
2131 |
||
2132 |
primcorec lapp :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
|
2133 |
"lapp xs ys = |
|
53644 | 2134 |
(case xs of |
2135 |
LNil \<Rightarrow> ys |
|
62081 | 2136 |
| LCons x xs' \<Rightarrow> LCons x (lapp xs' ys))" |
2137 |
||
2138 |
text \<open> |
|
53752 | 2139 |
\noindent |
62317 | 2140 |
For technical reasons, @{text "case"}--@{text "of"} is only supported for |
2141 |
case distinctions on (co)datatypes that provide discriminators and selectors. |
|
2142 |
||
54402 | 2143 |
Pattern matching is not supported by @{command primcorec}. Fortunately, it is |
62081 | 2144 |
easy to generate pattern-maching equations using the @{command simps_of_case} |
61304 | 2145 |
command provided by the theory @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"}. |
62081 | 2146 |
\<close> |
2147 |
||
2148 |
simps_of_case lapp_simps: lapp.code |
|
2149 |
||
2150 |
text \<open> |
|
2151 |
This generates the lemma collection @{thm [source] lapp_simps}: |
|
54402 | 2152 |
% |
62081 | 2153 |
\begin{gather*} |
2154 |
@{thm lapp_simps(1)[no_vars]} \\ |
|
2155 |
@{thm lapp_simps(2)[no_vars]} |
|
2156 |
\end{gather*} |
|
54402 | 2157 |
% |
53646 | 2158 |
Corecursion is useful to specify not only functions but also infinite objects: |
62081 | 2159 |
\<close> |
53646 | 2160 |
|
53826 | 2161 |
primcorec infty :: enat where |
58245 | 2162 |
"infty = ESucc infty" |
53644 | 2163 |
|
62081 | 2164 |
text \<open> |
53752 | 2165 |
\noindent |
2166 |
The example below constructs a pseudorandom process value. It takes a stream of |
|
53675 | 2167 |
actions (@{text s}), a pseudorandom function generator (@{text f}), and a |
2168 |
pseudorandom seed (@{text n}): |
|
62081 | 2169 |
\<close> |
53675 | 2170 |
|
59861 | 2171 |
(*<*) |
2172 |
context early |
|
2173 |
begin |
|
2174 |
(*>*) |
|
2175 |
primcorec |
|
53752 | 2176 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
2177 |
where |
|
53675 | 2178 |
"random_process s f n = |
2179 |
(if n mod 4 = 0 then |
|
2180 |
Fail |
|
2181 |
else if n mod 4 = 1 then |
|
2182 |
Skip (random_process s f (f n)) |
|
2183 |
else if n mod 4 = 2 then |
|
2184 |
Action (shd s) (random_process (stl s) f (f n)) |
|
2185 |
else |
|
2186 |
Choice (random_process (every_snd s) (f \<circ> f) (f n)) |
|
2187 |
(random_process (every_snd (stl s)) (f \<circ> f) (f (f n))))" |
|
59861 | 2188 |
(*<*) |
2189 |
end |
|
2190 |
(*>*) |
|
53675 | 2191 |
|
62081 | 2192 |
text \<open> |
53675 | 2193 |
\noindent |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2194 |
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
|
2195 |
sequentially. This is visible in the generated theorems. The constructor and |
53752 | 2196 |
destructor views offer nonsequential alternatives. |
62081 | 2197 |
\<close> |
2198 |
||
2199 |
||
2200 |
subsubsection \<open> Mutual Corecursion |
|
2201 |
\label{sssec:primcorec-mutual-corecursion} \<close> |
|
2202 |
||
2203 |
text \<open> |
|
53647 | 2204 |
The syntax for mutually corecursive functions over mutually corecursive |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2205 |
datatypes is unsurprising: |
62081 | 2206 |
\<close> |
53647 | 2207 |
|
53826 | 2208 |
primcorec |
53644 | 2209 |
even_infty :: even_enat and |
2210 |
odd_infty :: odd_enat |
|
2211 |
where |
|
62081 | 2212 |
"even_infty = Even_ESucc odd_infty" |
2213 |
| "odd_infty = Odd_ESucc even_infty" |
|
2214 |
||
2215 |
||
2216 |
subsubsection \<open> Nested Corecursion |
|
2217 |
\label{sssec:primcorec-nested-corecursion} \<close> |
|
2218 |
||
2219 |
text \<open> |
|
53647 | 2220 |
The next pair of examples generalize the @{const literate} and @{const siterate} |
2221 |
functions (Section~\ref{sssec:primcorec-nested-corecursion}) to possibly |
|
2222 |
infinite trees in which subnodes are organized either as a lazy list (@{text |
|
54072 | 2223 |
tree\<^sub>i\<^sub>i}) or as a finite set (@{text tree\<^sub>i\<^sub>s}). They rely on the map functions of |
2224 |
the nesting type constructors to lift the corecursive calls: |
|
62081 | 2225 |
\<close> |
53647 | 2226 |
|
53826 | 2227 |
primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
54072 | 2228 |
"iterate\<^sub>i\<^sub>i g x = Node\<^sub>i\<^sub>i x (lmap (iterate\<^sub>i\<^sub>i g) (g x))" |
53644 | 2229 |
|
62081 | 2230 |
text \<open> \blankline \<close> |
53677 | 2231 |
|
53826 | 2232 |
primcorec iterate\<^sub>i\<^sub>s :: "('a \<Rightarrow> 'a fset) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>s" where |
54072 | 2233 |
"iterate\<^sub>i\<^sub>s g x = Node\<^sub>i\<^sub>s x (fimage (iterate\<^sub>i\<^sub>s g) (g x))" |
53644 | 2234 |
|
62081 | 2235 |
text \<open> |
53752 | 2236 |
\noindent |
54072 | 2237 |
Both examples follow the usual format for constructor arguments associated |
2238 |
with nested recursive occurrences of the datatype. Consider |
|
2239 |
@{const iterate\<^sub>i\<^sub>i}. The term @{term "g x"} constructs an @{typ "'a llist"} |
|
2240 |
value, which is turned into an @{typ "'a tree\<^sub>i\<^sub>i llist"} value using |
|
2241 |
@{const lmap}. |
|
2242 |
||
2243 |
This format may sometimes feel artificial. The following function constructs |
|
2244 |
a tree with a single, infinite branch from a stream: |
|
62081 | 2245 |
\<close> |
54072 | 2246 |
|
2247 |
primcorec tree\<^sub>i\<^sub>i_of_stream :: "'a stream \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
|
2248 |
"tree\<^sub>i\<^sub>i_of_stream s = |
|
2249 |
Node\<^sub>i\<^sub>i (shd s) (lmap tree\<^sub>i\<^sub>i_of_stream (LCons (stl s) LNil))" |
|
2250 |
||
62081 | 2251 |
text \<open> |
54072 | 2252 |
\noindent |
54955
cf8d429dc24e
reintroduce recursive calls under constructors, taken out in 8dd0e0316881 mainly and in subsequent changes
blanchet
parents:
54832
diff
changeset
|
2253 |
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
|
2254 |
under constructors: |
62081 | 2255 |
\<close> |
54072 | 2256 |
|
54955
cf8d429dc24e
reintroduce recursive calls under constructors, taken out in 8dd0e0316881 mainly and in subsequent changes
blanchet
parents:
54832
diff
changeset
|
2257 |
primcorec (*<*)(in late) (*>*)tree\<^sub>i\<^sub>i_of_stream :: "'a stream \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
55350 | 2258 |
"tree\<^sub>i\<^sub>i_of_stream s = |
2259 |
Node\<^sub>i\<^sub>i (shd s) (LCons (tree\<^sub>i\<^sub>i_of_stream (stl s)) LNil)" |
|
54072 | 2260 |
|
62081 | 2261 |
text \<open> |
54072 | 2262 |
The next example illustrates corecursion through functions, which is a bit |
2263 |
special. Deterministic finite automata (DFAs) are traditionally defined as |
|
2264 |
5-tuples @{text "(Q, \<Sigma>, \<delta>, q\<^sub>0, F)"}, where @{text Q} is a finite set of states, |
|
53675 | 2265 |
@{text \<Sigma>} is a finite alphabet, @{text \<delta>} is a transition function, @{text q\<^sub>0} |
2266 |
is an initial state, and @{text F} is a set of final states. The following |
|
55350 | 2267 |
function translates a DFA into a state machine: |
62081 | 2268 |
\<close> |
53675 | 2269 |
|
55350 | 2270 |
primcorec (*<*)(in early) (*>*)sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2271 |
"sm_of_dfa \<delta> F q = SM (q \<in> F) (sm_of_dfa \<delta> F \<circ> \<delta> q)" |
|
53675 | 2272 |
|
62081 | 2273 |
text \<open> |
53751 | 2274 |
\noindent |
2275 |
The map function for the function type (@{text \<Rightarrow>}) is composition |
|
54181 | 2276 |
(@{text "op \<circ>"}). For convenience, corecursion through functions can |
54182 | 2277 |
also be expressed using $\lambda$-abstractions and function application rather |
54031 | 2278 |
than through composition. For example: |
62081 | 2279 |
\<close> |
53751 | 2280 |
|
55350 | 2281 |
primcorec sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2282 |
"sm_of_dfa \<delta> F q = SM (q \<in> F) (\<lambda>a. sm_of_dfa \<delta> F (\<delta> q a))" |
|
53752 | 2283 |
|
62081 | 2284 |
text \<open> \blankline \<close> |
53752 | 2285 |
|
55350 | 2286 |
primcorec empty_sm :: "'a sm" where |
2287 |
"empty_sm = SM False (\<lambda>_. empty_sm)" |
|
53751 | 2288 |
|
62081 | 2289 |
text \<open> \blankline \<close> |
53752 | 2290 |
|
55350 | 2291 |
primcorec not_sm :: "'a sm \<Rightarrow> 'a sm" where |
2292 |
"not_sm M = SM (\<not> accept M) (\<lambda>a. not_sm (trans M a))" |
|
53751 | 2293 |
|
62081 | 2294 |
text \<open> \blankline \<close> |
53752 | 2295 |
|
55350 | 2296 |
primcorec or_sm :: "'a sm \<Rightarrow> 'a sm \<Rightarrow> 'a sm" where |
2297 |
"or_sm M N = |
|
2298 |
SM (accept M \<or> accept N) (\<lambda>a. or_sm (trans M a) (trans N a))" |
|
53751 | 2299 |
|
62081 | 2300 |
text \<open> |
54182 | 2301 |
\noindent |
2302 |
For recursion through curried $n$-ary functions, $n$ applications of |
|
2303 |
@{term "op \<circ>"} are necessary. The examples below illustrate the case where |
|
2304 |
$n = 2$: |
|
62081 | 2305 |
\<close> |
54182 | 2306 |
|
55350 | 2307 |
codatatype ('a, 'b) sm2 = |
2308 |
SM2 (accept2: bool) (trans2: "'a \<Rightarrow> 'b \<Rightarrow> ('a, 'b) sm2") |
|
54182 | 2309 |
|
62081 | 2310 |
text \<open> \blankline \<close> |
54182 | 2311 |
|
2312 |
primcorec |
|
55350 | 2313 |
(*<*)(in early) (*>*)sm2_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> ('a, 'b) sm2" |
54182 | 2314 |
where |
55350 | 2315 |
"sm2_of_dfa \<delta> F q = SM2 (q \<in> F) (op \<circ> (op \<circ> (sm2_of_dfa \<delta> F)) (\<delta> q))" |
54182 | 2316 |
|
62081 | 2317 |
text \<open> \blankline \<close> |
54182 | 2318 |
|
2319 |
primcorec |
|
55350 | 2320 |
sm2_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> ('a, 'b) sm2" |
54182 | 2321 |
where |
55350 | 2322 |
"sm2_of_dfa \<delta> F q = SM2 (q \<in> F) (\<lambda>a b. sm2_of_dfa \<delta> F (\<delta> q a b))" |
54182 | 2323 |
|
53644 | 2324 |
|
62081 | 2325 |
subsubsection \<open> Nested-as-Mutual Corecursion |
2326 |
\label{sssec:primcorec-nested-as-mutual-corecursion} \<close> |
|
2327 |
||
2328 |
text \<open> |
|
53647 | 2329 |
Just as it is possible to recurse over nested recursive datatypes as if they |
2330 |
were mutually recursive |
|
2331 |
(Section~\ref{sssec:primrec-nested-as-mutual-recursion}), it is possible to |
|
53752 | 2332 |
pretend that nested codatatypes are mutually corecursive. For example: |
62081 | 2333 |
\<close> |
53647 | 2334 |
|
54287 | 2335 |
(*<*) |
2336 |
context late |
|
2337 |
begin |
|
2338 |
(*>*) |
|
54072 | 2339 |
primcorec |
54287 | 2340 |
iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" and |
53644 | 2341 |
iterates\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a llist \<Rightarrow> 'a tree\<^sub>i\<^sub>i llist" |
2342 |
where |
|
62081 | 2343 |
"iterate\<^sub>i\<^sub>i g x = Node\<^sub>i\<^sub>i x (iterates\<^sub>i\<^sub>i g (g x))" |
2344 |
| "iterates\<^sub>i\<^sub>i g xs = |
|
53644 | 2345 |
(case xs of |
2346 |
LNil \<Rightarrow> LNil |
|
54072 | 2347 |
| 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
|
2348 |
|
62081 | 2349 |
text \<open> |
54287 | 2350 |
\noindent |
2351 |
Coinduction rules are generated as |
|
2352 |
@{thm [source] iterate\<^sub>i\<^sub>i.coinduct}, |
|
2353 |
@{thm [source] iterates\<^sub>i\<^sub>i.coinduct}, and |
|
2354 |
@{thm [source] iterate\<^sub>i\<^sub>i_iterates\<^sub>i\<^sub>i.coinduct} |
|
57983
6edc3529bb4e
reordered some (co)datatype property names for more consistency
blanchet
parents:
57982
diff
changeset
|
2355 |
and analogously for @{text coinduct_strong}. These rules and the |
54287 | 2356 |
underlying corecursors are generated on a per-need basis and are kept in a cache |
2357 |
to speed up subsequent definitions. |
|
62081 | 2358 |
\<close> |
54287 | 2359 |
|
2360 |
(*<*) |
|
2361 |
end |
|
2362 |
(*>*) |
|
2363 |
||
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2364 |
|
62081 | 2365 |
subsubsection \<open> Constructor View |
2366 |
\label{ssec:primrec-constructor-view} \<close> |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2367 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2368 |
(*<*) |
54182 | 2369 |
locale ctr_view |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2370 |
begin |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2371 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2372 |
|
62081 | 2373 |
text \<open> |
53750 | 2374 |
The constructor view is similar to the code view, but there is one separate |
2375 |
conditional equation per constructor rather than a single unconditional |
|
2376 |
equation. Examples that rely on a single constructor, such as @{const literate} |
|
2377 |
and @{const siterate}, are identical in both styles. |
|
2378 |
||
2379 |
Here is an example where there is a difference: |
|
62081 | 2380 |
\<close> |
2381 |
||
2382 |
primcorec lapp :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
|
2383 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lapp xs ys = LNil" |
|
2384 |
| "_ \<Longrightarrow> lapp xs ys = LCons (lhd (if lnull xs then ys else xs)) |
|
2385 |
(if xs = LNil then ltl ys else lapp (ltl xs) ys)" |
|
2386 |
||
2387 |
text \<open> |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2388 |
\noindent |
53752 | 2389 |
With the constructor view, we must distinguish between the @{const LNil} and |
2390 |
the @{const LCons} case. The condition for @{const LCons} is |
|
2391 |
left implicit, as the negation of that for @{const LNil}. |
|
53750 | 2392 |
|
59861 | 2393 |
For this example, the constructor view is slightly more involved than the |
53750 | 2394 |
code equation. Recall the code view version presented in |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2395 |
Section~\ref{sssec:primcorec-simple-corecursion}. |
62081 | 2396 |
% TODO: \[{thm code_view.lapp.code}\] |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2397 |
The constructor view requires us to analyze the second argument (@{term ys}). |
53752 | 2398 |
The code equation generated from the constructor view also suffers from this. |
62081 | 2399 |
% TODO: \[{thm lapp.code}\] |
53750 | 2400 |
|
53752 | 2401 |
In contrast, the next example is arguably more naturally expressed in the |
2402 |
constructor view: |
|
62081 | 2403 |
\<close> |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2404 |
|
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2405 |
primcorec |
53752 | 2406 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
2407 |
where |
|
62081 | 2408 |
"n mod 4 = 0 \<Longrightarrow> random_process s f n = Fail" |
2409 |
| "n mod 4 = 1 \<Longrightarrow> |
|
2410 |
random_process s f n = Skip (random_process s f (f n))" |
|
2411 |
| "n mod 4 = 2 \<Longrightarrow> |
|
2412 |
random_process s f n = Action (shd s) (random_process (stl s) f (f n))" |
|
2413 |
| "n mod 4 = 3 \<Longrightarrow> |
|
53752 | 2414 |
random_process s f n = Choice (random_process (every_snd s) f (f n)) |
53826 | 2415 |
(random_process (every_snd (stl s)) f (f n))" |
2416 |
(*<*) |
|
53644 | 2417 |
end |
2418 |
(*>*) |
|
52805 | 2419 |
|
62081 | 2420 |
text \<open> |
53752 | 2421 |
\noindent |
53750 | 2422 |
Since there is no sequentiality, we can apply the equation for @{const Choice} |
61076 | 2423 |
without having first to discharge @{term "n mod (4::int) \<noteq> 0"}, |
2424 |
@{term "n mod (4::int) \<noteq> 1"}, and |
|
2425 |
@{term "n mod (4::int) \<noteq> 2"}. |
|
59284 | 2426 |
The price to pay for this elegance is that we must discharge exclusiveness proof |
53750 | 2427 |
obligations, one for each pair of conditions |
61076 | 2428 |
@{term "(n mod (4::int) = i, n mod (4::int) = j)"} |
53752 | 2429 |
with @{term "i < j"}. If we prefer not to discharge any obligations, we can |
2430 |
enable the @{text "sequential"} option. This pushes the problem to the users of |
|
2431 |
the generated properties. |
|
53750 | 2432 |
%Here are more examples to conclude: |
62081 | 2433 |
\<close> |
2434 |
||
2435 |
||
2436 |
subsubsection \<open> Destructor View |
|
2437 |
\label{ssec:primrec-destructor-view} \<close> |
|
53752 | 2438 |
|
2439 |
(*<*) |
|
54182 | 2440 |
locale dtr_view |
53752 | 2441 |
begin |
2442 |
(*>*) |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2443 |
|
62081 | 2444 |
text \<open> |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2445 |
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
|
2446 |
determine which constructor to choose, and these conditions are interpreted |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2447 |
sequentially or not depending on the @{text "sequential"} option. |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2448 |
Consider the following examples: |
62081 | 2449 |
\<close> |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2450 |
|
53826 | 2451 |
primcorec literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
62081 | 2452 |
"\<not> lnull (literate _ x)" |
2453 |
| "lhd (literate _ x) = x" |
|
2454 |
| "ltl (literate g x) = literate g (g x)" |
|
2455 |
||
2456 |
text \<open> \blankline \<close> |
|
53752 | 2457 |
|
53826 | 2458 |
primcorec siterate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a stream" where |
62081 | 2459 |
"shd (siterate _ x) = x" |
2460 |
| "stl (siterate g x) = siterate g (g x)" |
|
2461 |
||
2462 |
text \<open> \blankline \<close> |
|
53752 | 2463 |
|
53826 | 2464 |
primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
62081 | 2465 |
"shd (every_snd s) = shd s" |
2466 |
| "stl (every_snd s) = stl (stl s)" |
|
2467 |
||
2468 |
text \<open> |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2469 |
\noindent |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2470 |
The first formula in the @{const literate} specification indicates which |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2471 |
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
|
2472 |
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
|
2473 |
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
|
2474 |
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
|
2475 |
Their arguments are unrestricted. |
53750 | 2476 |
|
2477 |
The next example shows how to specify functions that rely on more than one |
|
2478 |
constructor: |
|
62081 | 2479 |
\<close> |
2480 |
||
2481 |
primcorec lapp :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
|
2482 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lnull (lapp xs ys)" |
|
2483 |
| "lhd (lapp xs ys) = lhd (if lnull xs then ys else xs)" |
|
2484 |
| "ltl (lapp xs ys) = (if xs = LNil then ltl ys else lapp (ltl xs) ys)" |
|
2485 |
||
2486 |
text \<open> |
|
53750 | 2487 |
\noindent |
2488 |
For a codatatype with $n$ constructors, it is sufficient to specify $n - 1$ |
|
2489 |
discriminator formulas. The command will then assume that the remaining |
|
2490 |
constructor should be taken otherwise. This can be made explicit by adding |
|
62081 | 2491 |
\<close> |
53750 | 2492 |
|
2493 |
(*<*) |
|
2494 |
end |
|
2495 |
||
54182 | 2496 |
locale dtr_view2 |
2497 |
begin |
|
2498 |
||
62081 | 2499 |
primcorec lapp :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
2500 |
"lnull xs \<Longrightarrow> lnull ys \<Longrightarrow> lnull (lapp xs ys)" |
|
2501 |
| "lhd (lapp xs ys) = lhd (if lnull xs then ys else xs)" |
|
2502 |
| "ltl (lapp xs ys) = (if xs = LNil then ltl ys else lapp (ltl xs) ys)" | |
|
53750 | 2503 |
(*>*) |
62081 | 2504 |
"_ \<Longrightarrow> \<not> lnull (lapp xs ys)" |
2505 |
||
2506 |
text \<open> |
|
53750 | 2507 |
\noindent |
53752 | 2508 |
to the specification. The generated selector theorems are conditional. |
2509 |
||
2510 |
The next example illustrates how to cope with selectors defined for several |
|
53750 | 2511 |
constructors: |
62081 | 2512 |
\<close> |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2513 |
|
53831
80423b9080cf
support "of" syntax to disambiguate selector equations
panny
parents:
53829
diff
changeset
|
2514 |
primcorec |
53752 | 2515 |
random_process :: "'a stream \<Rightarrow> (int \<Rightarrow> int) \<Rightarrow> int \<Rightarrow> 'a process" |
2516 |
where |
|
62081 | 2517 |
"n mod 4 = 0 \<Longrightarrow> random_process s f n = Fail" |
2518 |
| "n mod 4 = 1 \<Longrightarrow> is_Skip (random_process s f n)" |
|
2519 |
| "n mod 4 = 2 \<Longrightarrow> is_Action (random_process s f n)" |
|
2520 |
| "n mod 4 = 3 \<Longrightarrow> is_Choice (random_process s f n)" |
|
2521 |
| "cont (random_process s f n) = random_process s f (f n)" of Skip |
|
2522 |
| "prefix (random_process s f n) = shd s" |
|
2523 |
| "cont (random_process s f n) = random_process (stl s) f (f n)" of Action |
|
2524 |
| "left (random_process s f n) = random_process (every_snd s) f (f n)" |
|
2525 |
| "right (random_process s f n) = random_process (every_snd (stl s)) f (f n)" |
|
2526 |
||
2527 |
text \<open> |
|
53750 | 2528 |
\noindent |
2529 |
Using the @{text "of"} keyword, different equations are specified for @{const |
|
2530 |
cont} depending on which constructor is selected. |
|
2531 |
||
2532 |
Here are more examples to conclude: |
|
62081 | 2533 |
\<close> |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2534 |
|
53826 | 2535 |
primcorec |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2536 |
even_infty :: even_enat and |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2537 |
odd_infty :: odd_enat |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2538 |
where |
62081 | 2539 |
"even_infty \<noteq> Even_EZero" |
2540 |
| "un_Even_ESucc even_infty = odd_infty" |
|
2541 |
| "un_Odd_ESucc odd_infty = even_infty" |
|
2542 |
||
2543 |
text \<open> \blankline \<close> |
|
53752 | 2544 |
|
53826 | 2545 |
primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
62081 | 2546 |
"lbl\<^sub>i\<^sub>i (iterate\<^sub>i\<^sub>i g x) = x" |
2547 |
| "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
|
2548 |
(*<*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2549 |
end |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2550 |
(*>*) |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2551 |
|
53750 | 2552 |
|
62081 | 2553 |
subsection \<open> Command Syntax |
2554 |
\label{ssec:primcorec-command-syntax} \<close> |
|
2555 |
||
2556 |
subsubsection \<open> \keyw{primcorec} and \keyw{primcorecursive} |
|
2557 |
\label{sssec:primcorecursive-and-primcorec} \<close> |
|
2558 |
||
2559 |
text \<open> |
|
53829 | 2560 |
\begin{matharray}{rcl} |
2561 |
@{command_def "primcorec"} & : & @{text "local_theory \<rightarrow> local_theory"} \\ |
|
2562 |
@{command_def "primcorecursive"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2563 |
\end{matharray} |
|
52840 | 2564 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2565 |
@{rail \<open> |
55029
61a6bf7d4b02
clarified @{rail} syntax: prefer explicit \<newline> symbol;
wenzelm
parents:
54958
diff
changeset
|
2566 |
(@@{command primcorec} | @@{command primcorecursive}) target? \<newline> |
59277 | 2567 |
@{syntax pcr_options}? fixes @'where' (@{syntax pcr_formula} + '|') |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2568 |
; |
59282 | 2569 |
@{syntax_def pcr_options}: '(' ((@{syntax plugins} | 'sequential' | 'exhaustive' | 'transfer') + ',') ')' |
52840 | 2570 |
; |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2571 |
@{syntax_def pcr_formula}: thmdecl? prop (@'of' (term * ))? |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2572 |
\<close>} |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2573 |
|
55351 | 2574 |
\medskip |
2575 |
||
2576 |
\noindent |
|
55474 | 2577 |
The @{command primcorec} and @{command primcorecursive} commands introduce a set |
2578 |
of mutually corecursive functions over codatatypes. |
|
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2579 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2580 |
The syntactic entity \synt{target} can be used to specify a local context, |
55474 | 2581 |
\synt{fixes} denotes a list of names with optional type signatures, |
2582 |
\synt{thmdecl} denotes an optional name for the formula that follows, and |
|
58620 | 2583 |
\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
|
2584 |
|
59280 | 2585 |
The optional target is optionally followed by a combination of the following |
56124 | 2586 |
options: |
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2587 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2588 |
\begin{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2589 |
\setlength{\itemsep}{0pt} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2590 |
|
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2591 |
\item |
59282 | 2592 |
The @{text plugins} option indicates which plugins should be enabled |
2593 |
(@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
|
2594 |
||
2595 |
\item |
|
2596 |
The @{text sequential} option indicates that the conditions in specifications |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2597 |
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
|
2598 |
sequentially. |
53826 | 2599 |
|
2600 |
\item |
|
59282 | 2601 |
The @{text exhaustive} option indicates that the conditions in specifications |
53826 | 2602 |
expressed using the constructor or destructor view cover all possible cases. |
59284 | 2603 |
This generally gives rise to an additional proof obligation. |
59277 | 2604 |
|
2605 |
\item |
|
59282 | 2606 |
The @{text transfer} option indicates that an unconditional transfer rule |
59278 | 2607 |
should be generated and proved @{text "by transfer_prover"}. The |
2608 |
@{text "[transfer_rule]"} attribute is set on the generated theorem. |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2609 |
\end{itemize} |
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
2610 |
|
55474 | 2611 |
The @{command primcorec} command is an abbreviation for @{command |
2612 |
primcorecursive} with @{text "by auto?"} to discharge any emerging proof |
|
2613 |
obligations. |
|
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 |
%%% TODO: elaborate on format of the propositions |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2616 |
%%% TODO: elaborate on mutual and nested-to-mutual |
62081 | 2617 |
\<close> |
2618 |
||
2619 |
||
2620 |
subsection \<open> Generated Theorems |
|
2621 |
\label{ssec:primcorec-generated-theorems} \<close> |
|
2622 |
||
2623 |
text \<open> |
|
59284 | 2624 |
The @{command primcorec} and @{command primcorecursive} commands generate the |
2625 |
following properties (listed for @{const literate}): |
|
2626 |
||
2627 |
\begin{indentblock} |
|
2628 |
\begin{description} |
|
2629 |
||
2630 |
\item[@{text "f."}\hthm{code} @{text "[code]"}\rm:] ~ \\ |
|
2631 |
@{thm literate.code[no_vars]} \\ |
|
2632 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
|
2633 |
(Section~\ref{ssec:code-generator}). |
|
2634 |
||
2635 |
\item[@{text "f."}\hthm{ctr}\rm:] ~ \\ |
|
2636 |
@{thm literate.ctr[no_vars]} |
|
2637 |
||
2638 |
\item[@{text "f."}\hthm{disc} @{text "[simp, code]"}\rm:] ~ \\ |
|
2639 |
@{thm literate.disc[no_vars]} \\ |
|
2640 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
|
2641 |
(Section~\ref{ssec:code-generator}). The @{text "[simp]"} attribute is set only |
|
2642 |
for functions for which @{text f.disc_iff} is not available. |
|
2643 |
||
2644 |
\item[@{text "f."}\hthm{disc_iff} @{text "[simp]"}\rm:] ~ \\ |
|
2645 |
@{thm literate.disc_iff[no_vars]} \\ |
|
2646 |
This property is generated only for functions declared with the |
|
2647 |
@{text exhaustive} option or whose conditions are trivially exhaustive. |
|
2648 |
||
2649 |
\item[@{text "f."}\hthm{sel} @{text "[simp, code]"}\rm:] ~ \\ |
|
2650 |
@{thm literate.disc[no_vars]} \\ |
|
2651 |
The @{text "[code]"} attribute is set by the @{text code} plugin |
|
2652 |
(Section~\ref{ssec:code-generator}). |
|
2653 |
||
2654 |
\item[@{text "f."}\hthm{exclude}\rm:] ~ \\ |
|
2655 |
These properties are missing for @{const literate} because no exclusiveness |
|
2656 |
proof obligations arose. In general, the properties correspond to the |
|
2657 |
discharged proof obligations. |
|
2658 |
||
2659 |
\item[@{text "f."}\hthm{exhaust}\rm:] ~ \\ |
|
2660 |
This property is missing for @{const literate} because no exhaustiveness |
|
2661 |
proof obligation arose. In general, the property correspond to the discharged |
|
2662 |
proof obligation. |
|
2663 |
||
2664 |
\item[\begin{tabular}{@ {}l@ {}} |
|
2665 |
@{text "f."}\hthm{coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
2666 |
\phantom{@{text "f."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
2667 |
D\<^sub>n]"}\rm: |
|
2668 |
\end{tabular}] ~ \\ |
|
2669 |
This coinduction rule is generated for nested-as-mutual corecursive functions |
|
2670 |
(Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). |
|
2671 |
||
2672 |
\item[\begin{tabular}{@ {}l@ {}} |
|
2673 |
@{text "f."}\hthm{coinduct_strong} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
2674 |
\phantom{@{text "f."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
2675 |
D\<^sub>n]"}\rm: |
|
2676 |
\end{tabular}] ~ \\ |
|
2677 |
This coinduction rule is generated for nested-as-mutual corecursive functions |
|
2678 |
(Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). |
|
2679 |
||
2680 |
\item[\begin{tabular}{@ {}l@ {}} |
|
2681 |
@{text "f\<^sub>1_\<dots>_f\<^sub>m."}\hthm{coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
2682 |
\phantom{@{text "f."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
2683 |
D\<^sub>n]"}\rm: |
|
2684 |
\end{tabular}] ~ \\ |
|
2685 |
This coinduction rule is generated for nested-as-mutual corecursive functions |
|
2686 |
(Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). Given $m > 1$ |
|
2687 |
mutually corecursive functions, this rule can be used to prove $m$ properties |
|
2688 |
simultaneously. |
|
2689 |
||
2690 |
\item[\begin{tabular}{@ {}l@ {}} |
|
2691 |
@{text "f\<^sub>1_\<dots>_f\<^sub>m."}\hthm{coinduct_strong} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
|
2692 |
\phantom{@{text "f."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
|
2693 |
D\<^sub>n]"}\rm: |
|
2694 |
\end{tabular}] ~ \\ |
|
2695 |
This coinduction rule is generated for nested-as-mutual corecursive functions |
|
2696 |
(Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). Given $m > 1$ |
|
2697 |
mutually corecursive functions, this rule can be used to prove $m$ properties |
|
2698 |
simultaneously. |
|
2699 |
||
2700 |
\end{description} |
|
2701 |
\end{indentblock} |
|
2702 |
||
2703 |
\noindent |
|
2704 |
For convenience, @{command primcorec} and @{command primcorecursive} also |
|
2705 |
provide the following collection: |
|
2706 |
||
2707 |
\begin{indentblock} |
|
2708 |
\begin{description} |
|
2709 |
||
2710 |
\item[@{text "f."}\hthm{simps}] = @{text f.disc_iff} (or @{text f.disc}) @{text t.sel} |
|
2711 |
||
2712 |
\end{description} |
|
2713 |
\end{indentblock} |
|
62081 | 2714 |
\<close> |
52794 | 2715 |
|
2716 |
||
53623 | 2717 |
(* |
62081 | 2718 |
subsection \<open> Recursive Default Values for Selectors |
2719 |
\label{ssec:primcorec-recursive-default-values-for-selectors} \<close> |
|
2720 |
||
2721 |
text \<open> |
|
53623 | 2722 |
partial_function to the rescue |
62081 | 2723 |
\<close> |
53623 | 2724 |
*) |
2725 |
||
2726 |
||
62081 | 2727 |
section \<open> Registering Bounded Natural Functors |
2728 |
\label{sec:registering-bounded-natural-functors} \<close> |
|
2729 |
||
2730 |
text \<open> |
|
53647 | 2731 |
The (co)datatype package can be set up to allow nested recursion through |
55350 | 2732 |
arbitrary type constructors, as long as they adhere to the BNF requirements |
2733 |
and are registered as BNFs. It is also possible to declare a BNF abstractly |
|
2734 |
without specifying its internal structure. |
|
62081 | 2735 |
\<close> |
2736 |
||
2737 |
||
2738 |
subsection \<open> Bounded Natural Functors |
|
2739 |
\label{ssec:bounded-natural-functors} \<close> |
|
2740 |
||
2741 |
text \<open> |
|
55350 | 2742 |
Bounded natural functors (BNFs) are a semantic criterion for where |
2743 |
(co)re\-cur\-sion may appear on the right-hand side of an equation |
|
60146 | 2744 |
@{cite "traytel-et-al-2012" and "blanchette-et-al-2015-wit"}. |
55350 | 2745 |
|
2746 |
An $n$-ary BNF is a type constructor equipped with a map function |
|
2747 |
(functorial action), $n$ set functions (natural transformations), |
|
2748 |
and an infinite cardinal bound that satisfy certain properties. |
|
2749 |
For example, @{typ "'a llist"} is a unary BNF. |
|
62330 | 2750 |
Its predicator @{text "llist_all :: |
2751 |
('a \<Rightarrow> bool) \<Rightarrow> |
|
2752 |
'a llist \<Rightarrow> bool"} |
|
2753 |
extends unary predicates over elements to unary predicates over |
|
2754 |
lazy lists. |
|
2755 |
Similarly, its relator @{text "llist_all2 :: |
|
55350 | 2756 |
('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> |
2757 |
'a llist \<Rightarrow> 'b llist \<Rightarrow> bool"} |
|
2758 |
extends binary predicates over elements to binary predicates over parallel |
|
2759 |
lazy lists. The cardinal bound limits the number of elements returned by the |
|
2760 |
set function; it may not depend on the cardinality of @{typ 'a}. |
|
2761 |
||
58310 | 2762 |
The type constructors introduced by @{command datatype} and |
55350 | 2763 |
@{command codatatype} are automatically registered as BNFs. In addition, a |
2764 |
number of old-style datatypes and non-free types are preregistered. |
|
2765 |
||
2766 |
Given an $n$-ary BNF, the $n$ type variables associated with set functions, |
|
2767 |
and on which the map function acts, are \emph{live}; any other variables are |
|
2768 |
\emph{dead}. Nested (co)recursion can only take place through live variables. |
|
62081 | 2769 |
\<close> |
2770 |
||
2771 |
||
2772 |
subsection \<open> Introductory Examples |
|
2773 |
\label{ssec:bnf-introductory-examples} \<close> |
|
2774 |
||
2775 |
text \<open> |
|
55350 | 2776 |
The example below shows how to register a type as a BNF using the @{command bnf} |
2777 |
command. Some of the proof obligations are best viewed with the theory |
|
61304 | 2778 |
@{file "~~/src/HOL/Library/Cardinal_Notations.thy"} imported. |
55350 | 2779 |
|
2780 |
The type is simply a copy of the function space @{typ "'d \<Rightarrow> 'a"}, where @{typ 'a} |
|
2781 |
is live and @{typ 'd} is dead. We introduce it together with its map function, |
|
62330 | 2782 |
set function, predicator, and relator. |
62081 | 2783 |
\<close> |
55350 | 2784 |
|
61076 | 2785 |
typedef ('d, 'a) fn = "UNIV :: ('d \<Rightarrow> 'a) set" |
60152 | 2786 |
by simp |
2787 |
||
62081 | 2788 |
text \<open> \blankline \<close> |
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2789 |
|
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2790 |
setup_lifting type_definition_fn |
55350 | 2791 |
|
62081 | 2792 |
text \<open> \blankline \<close> |
55350 | 2793 |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2794 |
lift_definition map_fn :: "('a \<Rightarrow> 'b) \<Rightarrow> ('d, 'a) fn \<Rightarrow> ('d, 'b) fn" is "op \<circ>" . |
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2795 |
lift_definition set_fn :: "('d, 'a) fn \<Rightarrow> 'a set" is range . |
55350 | 2796 |
|
62081 | 2797 |
text \<open> \blankline \<close> |
55350 | 2798 |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2799 |
lift_definition |
62330 | 2800 |
pred_fn :: "('a \<Rightarrow> bool) \<Rightarrow> ('d, 'a) fn \<Rightarrow> bool" |
2801 |
is |
|
2802 |
"pred_fun (\<lambda>_. True)" . |
|
2803 |
||
2804 |
lift_definition |
|
55350 | 2805 |
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
|
2806 |
is |
55945 | 2807 |
"rel_fun (op =)" . |
55350 | 2808 |
|
62081 | 2809 |
text \<open> \blankline \<close> |
55350 | 2810 |
|
2811 |
bnf "('d, 'a) fn" |
|
2812 |
map: map_fn |
|
2813 |
sets: set_fn |
|
2814 |
bd: "natLeq +c |UNIV :: 'd set|" |
|
2815 |
rel: rel_fn |
|
62330 | 2816 |
pred: pred_fn |
55350 | 2817 |
proof - |
2818 |
show "map_fn id = id" |
|
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2819 |
by transfer auto |
55350 | 2820 |
next |
60136 | 2821 |
fix f :: "'a \<Rightarrow> 'b" and g :: "'b \<Rightarrow> 'c" |
2822 |
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
|
2823 |
by transfer (auto simp add: comp_def) |
55350 | 2824 |
next |
60136 | 2825 |
fix F :: "('d, 'a) fn" and f g :: "'a \<Rightarrow> 'b" |
55350 | 2826 |
assume "\<And>x. x \<in> set_fn F \<Longrightarrow> f x = g x" |
61303 | 2827 |
then show "map_fn f F = map_fn g F" |
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2828 |
by transfer auto |
55350 | 2829 |
next |
60136 | 2830 |
fix f :: "'a \<Rightarrow> 'b" |
2831 |
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
|
2832 |
by transfer (auto simp add: comp_def) |
55350 | 2833 |
next |
61076 | 2834 |
show "card_order (natLeq +c |UNIV :: 'd set| )" |
55350 | 2835 |
apply (rule card_order_csum) |
2836 |
apply (rule natLeq_card_order) |
|
2837 |
by (rule card_of_card_order_on) |
|
2838 |
next |
|
61076 | 2839 |
show "cinfinite (natLeq +c |UNIV :: 'd set| )" |
55350 | 2840 |
apply (rule cinfinite_csum) |
2841 |
apply (rule disjI1) |
|
2842 |
by (rule natLeq_cinfinite) |
|
2843 |
next |
|
2844 |
fix F :: "('d, 'a) fn" |
|
61076 | 2845 |
have "|set_fn F| \<le>o |UNIV :: 'd set|" (is "_ \<le>o ?U") |
55459
1cd927ca8296
cleaner, complete proof in documentation, contributed by Dmitriy T.
blanchet
parents:
55410
diff
changeset
|
2846 |
by transfer (rule card_of_image) |
55350 | 2847 |
also have "?U \<le>o natLeq +c ?U" |
2848 |
by (rule ordLeq_csum2) (rule card_of_Card_order) |
|
61076 | 2849 |
finally show "|set_fn F| \<le>o natLeq +c |UNIV :: 'd set|" . |
55350 | 2850 |
next |
60136 | 2851 |
fix R :: "'a \<Rightarrow> 'b \<Rightarrow> bool" and S :: "'b \<Rightarrow> 'c \<Rightarrow> bool" |
55350 | 2852 |
show "rel_fn R OO rel_fn S \<le> rel_fn (R OO S)" |
55945 | 2853 |
by (rule, transfer) (auto simp add: rel_fun_def) |
55350 | 2854 |
next |
60136 | 2855 |
fix R :: "'a \<Rightarrow> 'b \<Rightarrow> bool" |
62324 | 2856 |
show "rel_fn R = (\<lambda>x y. \<exists>z. set_fn z \<subseteq> {(x, y). R x y} \<and> map_fn fst z = x \<and> map_fn snd z = y)" |
2857 |
unfolding fun_eq_iff relcompp.simps conversep.simps |
|
2858 |
by transfer (force simp: rel_fun_def subset_iff) |
|
62330 | 2859 |
next |
2860 |
fix P :: "'a \<Rightarrow> bool" |
|
2861 |
show "pred_fn P = (\<lambda>x. Ball (set_fn x) P)" |
|
2862 |
unfolding fun_eq_iff by transfer simp |
|
55350 | 2863 |
qed |
2864 |
||
62081 | 2865 |
text \<open> \blankline \<close> |
55350 | 2866 |
|
2867 |
print_theorems |
|
2868 |
print_bnfs |
|
2869 |
||
62081 | 2870 |
text \<open> |
55350 | 2871 |
\noindent |
58931 | 2872 |
Using \keyw{print_theorems} and @{command print_bnfs}, we can contemplate and |
55350 | 2873 |
show the world what we have achieved. |
2874 |
||
2875 |
This particular example does not need any nonemptiness witness, because the |
|
2876 |
one generated by default is good enough, but in general this would be |
|
61304 | 2877 |
necessary. See @{file "~~/src/HOL/Basic_BNFs.thy"}, |
62081 | 2878 |
@{file "~~/src/HOL/Library/Countable_Set_Type.thy"}, |
61304 | 2879 |
@{file "~~/src/HOL/Library/FSet.thy"}, and |
2880 |
@{file "~~/src/HOL/Library/Multiset.thy"} for further examples of BNF |
|
2881 |
registration, some of which feature custom witnesses. |
|
55350 | 2882 |
|
61303 | 2883 |
For many typedefs, lifting the BNF structure from the raw type to the abstract |
2884 |
type can be done uniformly. This is the task of the @{command lift_bnf} command. |
|
2885 |
Using @{command lift_bnf}, the above registration of @{typ "('d, 'a) fn"} as a |
|
2886 |
BNF becomes much shorter: |
|
62081 | 2887 |
\<close> |
60920 | 2888 |
|
61303 | 2889 |
(*<*) |
2890 |
context early |
|
2891 |
begin |
|
2892 |
(*>*) |
|
2893 |
lift_bnf (*<*)(no_warn_wits) (*>*)('d, 'a) fn |
|
2894 |
by auto |
|
2895 |
(*<*) |
|
2896 |
end |
|
2897 |
(*>*) |
|
60920 | 2898 |
|
62081 | 2899 |
text \<open> |
61303 | 2900 |
For type copies (@{command typedef}s with @{term UNIV} as the representing set), |
2901 |
the proof obligations are so simple that they can be |
|
2902 |
discharged automatically, yielding another command, @{command copy_bnf}, which |
|
2903 |
does not emit any proof obligations: |
|
62081 | 2904 |
\<close> |
60920 | 2905 |
|
61303 | 2906 |
(*<*) |
2907 |
context late |
|
2908 |
begin |
|
2909 |
(*>*) |
|
60920 | 2910 |
copy_bnf ('d, 'a) fn |
61303 | 2911 |
(*<*) |
2912 |
end |
|
2913 |
(*>*) |
|
60920 | 2914 |
|
62081 | 2915 |
text \<open> |
61303 | 2916 |
Since record schemas are type copies, @{command copy_bnf} can be used to |
2917 |
register them as BNFs: |
|
62081 | 2918 |
\<close> |
60920 | 2919 |
|
2920 |
record 'a point = |
|
2921 |
xval :: 'a |
|
2922 |
yval :: 'a |
|
61303 | 2923 |
|
62081 | 2924 |
text \<open> \blankline \<close> |
60920 | 2925 |
|
2926 |
copy_bnf ('a, 'z) point_ext |
|
2927 |
||
62081 | 2928 |
text \<open> |
61303 | 2929 |
In the general case, the proof obligations generated by @{command lift_bnf} are |
2930 |
simpler than the acual BNF properties. In particular, no cardinality reasoning |
|
2931 |
is required. Consider the following type of nonempty lists: |
|
62081 | 2932 |
\<close> |
60920 | 2933 |
|
2934 |
typedef 'a nonempty_list = "{xs :: 'a list. xs \<noteq> []}" by auto |
|
2935 |
||
62081 | 2936 |
text \<open> |
61303 | 2937 |
The @{command lift_bnf} command requires us to prove that the set of nonempty lists |
2938 |
is closed under the map function and the zip function. The latter only |
|
60920 | 2939 |
occurs implicitly in the goal, in form of the variable |
61303 | 2940 |
@{term "zs :: ('a \<times> 'b) list"}. |
62081 | 2941 |
\<close> |
60920 | 2942 |
|
61303 | 2943 |
lift_bnf (*<*)(no_warn_wits) (*>*)'a nonempty_list |
60920 | 2944 |
proof - |
62330 | 2945 |
fix f (*<*):: "'a \<Rightarrow> 'c"(*>*)and xs :: "'a list" |
60920 | 2946 |
assume "xs \<in> {xs. xs \<noteq> []}" |
61303 | 2947 |
then show "map f xs \<in> {xs. xs \<noteq> []}" |
2948 |
by (cases xs(*<*) rule: list.exhaust(*>*)) auto |
|
60920 | 2949 |
next |
2950 |
fix zs :: "('a \<times> 'b) list" |
|
2951 |
assume "map fst zs \<in> {xs. xs \<noteq> []}" "map snd zs \<in> {xs. xs \<noteq> []}" |
|
61303 | 2952 |
then show "zs \<in> {xs. xs \<noteq> []}" |
2953 |
by (cases zs (*<*)rule: list.exhaust(*>*)) auto |
|
60920 | 2954 |
qed |
2955 |
||
62081 | 2956 |
text \<open> |
57542 | 2957 |
The next example declares a BNF axiomatically. This can be convenient for |
2958 |
reasoning abstractly about an arbitrary BNF. The @{command bnf_axiomatization} |
|
2959 |
command below introduces a type @{text "('a, 'b, 'c) F"}, three set constants, |
|
62330 | 2960 |
a map function, a predicator, a relator, and a nonemptiness witness that depends only on |
59284 | 2961 |
@{typ 'a}. The type @{text "'a \<Rightarrow> ('a, 'b, 'c) F"} of the witness can be read |
2962 |
as an implication: Given a witness for @{typ 'a}, we can construct a witness for |
|
2963 |
@{text "('a, 'b, 'c) F"}. The BNF properties are postulated as axioms. |
|
62081 | 2964 |
\<close> |
55350 | 2965 |
|
57542 | 2966 |
bnf_axiomatization (setA: 'a, setB: 'b, setC: 'c) F |
2967 |
[wits: "'a \<Rightarrow> ('a, 'b, 'c) F"] |
|
55350 | 2968 |
|
62081 | 2969 |
text \<open> \blankline \<close> |
55350 | 2970 |
|
2971 |
print_theorems |
|
2972 |
print_bnfs |
|
52794 | 2973 |
|
52824 | 2974 |
|
62081 | 2975 |
subsection \<open> Command Syntax |
2976 |
\label{ssec:bnf-command-syntax} \<close> |
|
2977 |
||
2978 |
subsubsection \<open> \keyw{bnf} |
|
2979 |
\label{sssec:bnf} \<close> |
|
2980 |
||
2981 |
text \<open> |
|
53829 | 2982 |
\begin{matharray}{rcl} |
2983 |
@{command_def "bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
|
2984 |
\end{matharray} |
|
2985 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2986 |
@{rail \<open> |
55474 | 2987 |
@@{command bnf} target? (name ':')? type \<newline> |
55029
61a6bf7d4b02
clarified @{rail} syntax: prefer explicit \<newline> symbol;
wenzelm
parents:
54958
diff
changeset
|
2988 |
'map:' term ('sets:' (term +))? 'bd:' term \<newline> |
58190 | 2989 |
('wits:' (term +))? ('rel:' term)? \<newline> |
2990 |
@{syntax plugins}? |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
2991 |
\<close>} |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2992 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2993 |
\medskip |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2994 |
|
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2995 |
\noindent |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2996 |
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
|
2997 |
functor (BNF). The type must be equipped with an appropriate map function |
62330 | 2998 |
(functorial action). In addition, custom set functions, predicators, relators, and |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
2999 |
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
|
3000 |
|
55474 | 3001 |
The syntactic entity \synt{target} can be used to specify a local context, |
3002 |
\synt{type} denotes a HOL type, and \synt{term} denotes a HOL term |
|
58620 | 3003 |
@{cite "isabelle-isar-ref"}. |
55474 | 3004 |
|
59280 | 3005 |
The @{syntax plugins} option indicates which plugins should be enabled |
3006 |
(@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
|
3007 |
||
55474 | 3008 |
%%% TODO: elaborate on proof obligations |
62081 | 3009 |
\<close> |
3010 |
||
3011 |
subsubsection \<open> \keyw{lift_bnf} |
|
3012 |
\label{sssec:lift-bnf} \<close> |
|
3013 |
||
3014 |
text \<open> |
|
60920 | 3015 |
\begin{matharray}{rcl} |
61303 | 3016 |
@{command_def "lift_bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
60920 | 3017 |
\end{matharray} |
3018 |
||
3019 |
@{rail \<open> |
|
3020 |
@@{command lift_bnf} target? lb_options? \<newline> |
|
3021 |
@{syntax tyargs} name wit_terms? \<newline> |
|
62081 | 3022 |
('via' thmref)? @{syntax map_rel}? |
60920 | 3023 |
; |
3024 |
@{syntax_def lb_options}: '(' ((@{syntax plugins} | 'no_warn_wits') + ',') ')' |
|
3025 |
; |
|
3026 |
@{syntax_def wit_terms}: '[' 'wits' ':' terms ']' |
|
61303 | 3027 |
\<close>} |
3028 |
\medskip |
|
3029 |
||
3030 |
\noindent |
|
3031 |
The @{command lift_bnf} command registers as a BNF an existing type (the |
|
3032 |
\emph{abstract type}) that was defined as a subtype of a BNF (the \emph{raw |
|
3033 |
type}) using the @{command typedef} command. To achieve this, it lifts the BNF |
|
3034 |
structure on the raw type to the abstract type following a @{term |
|
3035 |
type_definition} theorem. The theorem is usually inferred from the type, but can |
|
3036 |
also be explicitly supplied by means of the optional @{text via} clause. In |
|
62330 | 3037 |
addition, custom names for the set functions, the map function, the predicator, and the relator, |
61303 | 3038 |
as well as nonemptiness witnesses can be specified. |
3039 |
||
3040 |
Nonemptiness witnesses are not lifted from the raw type's BNF, as this would be |
|
3041 |
incomplete. They must be given as terms (on the raw type) and proved to be |
|
3042 |
witnesses. The command warns about witness types that are present in the raw |
|
3043 |
type's BNF but not supplied by the user. The warning can be disabled by |
|
3044 |
specifying the @{text no_warn_wits} option. |
|
62081 | 3045 |
\<close> |
3046 |
||
3047 |
subsubsection \<open> \keyw{copy_bnf} |
|
3048 |
\label{sssec:copy-bnf} \<close> |
|
3049 |
||
3050 |
text \<open> |
|
61303 | 3051 |
\begin{matharray}{rcl} |
3052 |
@{command_def "copy_bnf"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
3053 |
\end{matharray} |
|
3054 |
||
3055 |
@{rail \<open> |
|
60920 | 3056 |
@@{command copy_bnf} target? ('(' @{syntax plugins} ')')? \<newline> |
62081 | 3057 |
@{syntax tyargs} name ('via' thmref)? @{syntax map_rel}? |
60920 | 3058 |
\<close>} |
3059 |
\medskip |
|
3060 |
||
3061 |
\noindent |
|
61303 | 3062 |
The @{command copy_bnf} command performs the same lifting as @{command lift_bnf} |
3063 |
for type copies (@{command typedef}s with @{term UNIV} as the representing set), |
|
3064 |
without requiring the user to discharge any proof obligations or provide |
|
3065 |
nonemptiness witnesses. |
|
62081 | 3066 |
\<close> |
3067 |
||
3068 |
subsubsection \<open> \keyw{bnf_axiomatization} |
|
3069 |
\label{sssec:bnf-axiomatization} \<close> |
|
3070 |
||
3071 |
text \<open> |
|
54187 | 3072 |
\begin{matharray}{rcl} |
56942 | 3073 |
@{command_def "bnf_axiomatization"} & : & @{text "local_theory \<rightarrow> local_theory"} |
54187 | 3074 |
\end{matharray} |
3075 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
3076 |
@{rail \<open> |
59280 | 3077 |
@@{command bnf_axiomatization} target? ('(' @{syntax plugins} ')')? \<newline> |
58190 | 3078 |
@{syntax tyargs}? name @{syntax wit_types}? \<newline> |
3079 |
mixfix? @{syntax map_rel}? |
|
54602 | 3080 |
; |
55350 | 3081 |
@{syntax_def wit_types}: '[' 'wits' ':' types ']' |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
3082 |
\<close>} |
54602 | 3083 |
|
55351 | 3084 |
\medskip |
3085 |
||
55350 | 3086 |
\noindent |
56942 | 3087 |
The @{command bnf_axiomatization} command declares a new type and associated constants |
62330 | 3088 |
(map, set, predicator, 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
|
3089 |
these constants as axioms. |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
3090 |
|
55474 | 3091 |
The syntactic entity \synt{target} can be used to specify a local context, |
3092 |
\synt{name} denotes an identifier, \synt{typefree} denotes fixed type variable |
|
3093 |
(@{typ 'a}, @{typ 'b}, \ldots), and \synt{mixfix} denotes the usual |
|
58620 | 3094 |
parenthesized mixfix notation @{cite "isabelle-isar-ref"}. |
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
3095 |
|
59280 | 3096 |
The @{syntax plugins} option indicates which plugins should be enabled |
3097 |
(@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
|
3098 |
||
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
3099 |
Type arguments are live by default; they can be marked as dead by entering |
58220 | 3100 |
@{text dead} in front of the type variable (e.g., @{text "(dead 'a)"}) |
57092 | 3101 |
instead of an identifier for the corresponding set function. Witnesses can be |
3102 |
specified by their types. Otherwise, the syntax of @{command bnf_axiomatization} |
|
58310 | 3103 |
is identical to the left-hand side of a @{command datatype} or |
57092 | 3104 |
@{command codatatype} definition. |
55350 | 3105 |
|
3106 |
The command is useful to reason abstractly about BNFs. The axioms are safe |
|
57575 | 3107 |
because there exist BNFs of arbitrary large arities. Applications must import |
61304 | 3108 |
the @{file "~~/src/HOL/Library/BNF_Axiomatization.thy"} theory |
3109 |
to use this functionality. |
|
62081 | 3110 |
\<close> |
3111 |
||
3112 |
||
3113 |
subsubsection \<open> \keyw{print_bnfs} |
|
3114 |
\label{sssec:print-bnfs} \<close> |
|
3115 |
||
3116 |
text \<open> |
|
53829 | 3117 |
\begin{matharray}{rcl} |
3118 |
@{command_def "print_bnfs"} & : & @{text "local_theory \<rightarrow>"} |
|
3119 |
\end{matharray} |
|
3120 |
||
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
3121 |
@{rail \<open> |
53829 | 3122 |
@@{command print_bnfs} |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
3123 |
\<close>} |
62081 | 3124 |
\<close> |
3125 |
||
3126 |
||
3127 |
section \<open> Deriving Destructors and Theorems for Free Constructors |
|
3128 |
\label{sec:deriving-destructors-and-theorems-for-free-constructors} \<close> |
|
3129 |
||
3130 |
text \<open> |
|
53623 | 3131 |
The derivation of convenience theorems for types equipped with free constructors, |
58310 | 3132 |
as performed internally by @{command datatype} and @{command codatatype}, |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
3133 |
is available as a stand-alone command called @{command free_constructors}. |
52794 | 3134 |
|
53617 | 3135 |
% * need for this is rare but may arise if you want e.g. to add destructors to |
3136 |
% a type not introduced by ... |
|
3137 |
% |
|
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
3138 |
% * @{command free_constructors} |
58192 | 3139 |
% * @{text plugins}, @{text discs_sels} |
53617 | 3140 |
% * hack to have both co and nonco view via locale (cf. ext nats) |
62081 | 3141 |
\<close> |
52792 | 3142 |
|
52824 | 3143 |
|
53619 | 3144 |
(* |
62081 | 3145 |
subsection \<open> Introductory Example |
3146 |
\label{ssec:ctors-introductory-example} \<close> |
|
53619 | 3147 |
*) |
52794 | 3148 |
|
52824 | 3149 |
|
62081 | 3150 |
subsection \<open> Command Syntax |
3151 |
\label{ssec:ctors-command-syntax} \<close> |
|
3152 |
||
3153 |
subsubsection \<open> \keyw{free_constructors} |
|
3154 |
\label{sssec:free-constructors} \<close> |
|
3155 |
||
3156 |
text \<open> |
|
53829 | 3157 |
\begin{matharray}{rcl} |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
3158 |
@{command_def "free_constructors"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
53829 | 3159 |
\end{matharray} |
53018 | 3160 |
|
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
3161 |
@{rail \<open> |
55468
98b25c51e9e5
renamed 'wrap_free_constructors' to 'free_constructors' (cf. 'functor', 'bnf', etc.)
blanchet
parents:
55460
diff
changeset
|
3162 |
@@{command free_constructors} target? @{syntax dt_options} \<newline> |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
3163 |
name 'for' (@{syntax fc_ctor} + '|') \<newline> |
57206
d9be905d6283
changed syntax of map: and rel: arguments to BNF-based datatypes
blanchet
parents:
57200
diff
changeset
|
3164 |
(@'where' (prop + '|'))? |
53018 | 3165 |
; |
57200
aab87ffa60cc
use 'where' clause for selector default value syntax
blanchet
parents:
57153
diff
changeset
|
3166 |
@{syntax_def fc_ctor}: (name ':')? term (name * ) |
55112
b1a5d603fd12
prefer rail cartouche -- avoid back-slashed quotes;
wenzelm
parents:
55029
diff
changeset
|
3167 |
\<close>} |
53018 | 3168 |
|
55351 | 3169 |
\medskip |
3170 |
||
55460
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
3171 |
\noindent |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
3172 |
The @{command free_constructors} command generates destructor constants for |
3f4efd7d950d
added a bit of documentation for the different commands
blanchet
parents:
55459
diff
changeset
|
3173 |
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
|
3174 |
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
|
3175 |
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
|
3176 |
|
55474 | 3177 |
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
|
3178 |
\synt{name} denotes an identifier, \synt{prop} denotes a HOL proposition, and |
58620 | 3179 |
\synt{term} denotes a HOL term @{cite "isabelle-isar-ref"}. |
55474 | 3180 |
|
58310 | 3181 |
The syntax resembles that of @{command datatype} and @{command codatatype} |
55474 | 3182 |
definitions (Sections |
3183 |
\ref{ssec:datatype-command-syntax}~and~\ref{ssec:codatatype-command-syntax}). |
|
3184 |
A constructor is specified by an optional name for the discriminator, the |
|
3185 |
constructor itself (as a term), and a list of optional names for the selectors. |
|
53028 | 3186 |
|
53542 | 3187 |
Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems. |
57542 | 3188 |
For bootstrapping reasons, the generally useful @{text "[fundef_cong]"} |
3189 |
attribute is not set on the generated @{text case_cong} theorem. It can be |
|
3190 |
added manually using \keyw{declare}. |
|
62081 | 3191 |
\<close> |
3192 |
||
3193 |
||
3194 |
subsubsection \<open> \keyw{simps_of_case} |
|
3195 |
\label{sssec:simps-of-case} \<close> |
|
3196 |
||
3197 |
text \<open> |
|
3198 |
\begin{matharray}{rcl} |
|
3199 |
@{command_def "simps_of_case"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
3200 |
\end{matharray} |
|
3201 |
||
3202 |
@{rail \<open> |
|
3203 |
@@{command simps_of_case} target? (name ':')? \<newline> |
|
3204 |
(thmref + ) (@'splits' ':' (thmref + ))? |
|
3205 |
\<close>} |
|
3206 |
||
3207 |
\medskip |
|
3208 |
||
3209 |
\noindent |
|
3210 |
The @{command simps_of_case} command provided by theory |
|
3211 |
@{file "~~/src/HOL/Library/Simps_Case_Conv.thy"} converts a single equation with |
|
3212 |
a complex case expression on the right-hand side into a set of pattern-matching |
|
3213 |
equations. For example, |
|
3214 |
\<close> |
|
3215 |
||
3216 |
(*<*) |
|
3217 |
context late |
|
3218 |
begin |
|
3219 |
(*>*) |
|
3220 |
simps_of_case lapp_simps: lapp.code |
|
3221 |
||
3222 |
text \<open> |
|
3223 |
\noindent |
|
3224 |
translates @{thm lapp.code[no_vars]} into |
|
3225 |
% |
|
3226 |
\begin{gather*} |
|
3227 |
@{thm lapp_simps(1)[no_vars]} \\ |
|
3228 |
@{thm lapp_simps(2)[no_vars]} |
|
3229 |
\end{gather*} |
|
3230 |
\<close> |
|
3231 |
||
3232 |
||
3233 |
subsubsection \<open> \keyw{case_of_simps} |
|
3234 |
\label{sssec:case-of-simps} \<close> |
|
3235 |
||
3236 |
text \<open> |
|
3237 |
\begin{matharray}{rcl} |
|
3238 |
@{command_def "case_of_simps"} & : & @{text "local_theory \<rightarrow> local_theory"} |
|
3239 |
\end{matharray} |
|
3240 |
||
3241 |
@{rail \<open> |
|
3242 |
@@{command case_of_simps} target? (name ':')? \<newline> |
|
3243 |
(thmref + ) |
|
3244 |
\<close>} |
|
3245 |
||
3246 |
\medskip |
|
3247 |
||
3248 |
\noindent |
|
3249 |
The \keyw{case_of_simps} command provided by theory |
|
3250 |
@{file "~~/src/HOL/Library/Simps_Case_Conv.thy"} converts a set of |
|
3251 |
pattern-matching equations into single equation with a complex case expression |
|
3252 |
on the right-hand side (cf.\ @{command simps_of_case}). For example, |
|
3253 |
\<close> |
|
3254 |
||
3255 |
case_of_simps lapp_case: lapp_simps |
|
3256 |
||
3257 |
text \<open> |
|
3258 |
\noindent |
|
3259 |
translates |
|
3260 |
% |
|
3261 |
\begin{gather*} |
|
3262 |
@{thm lapp_simps(1)[no_vars]} \\ |
|
3263 |
@{thm lapp_simps(2)[no_vars]} |
|
3264 |
\end{gather*} |
|
3265 |
% |
|
3266 |
into @{thm lapp_case[no_vars]}. |
|
3267 |
\<close> |
|
3268 |
(*<*) |
|
3269 |
end |
|
3270 |
(*>*) |
|
52828 | 3271 |
|
52794 | 3272 |
|
53617 | 3273 |
(* |
62081 | 3274 |
section \<open> Using the Standard ML Interface |
3275 |
\label{sec:using-the-standard-ml-interface} \<close> |
|
3276 |
||
3277 |
text \<open> |
|
53623 | 3278 |
The package's programmatic interface. |
62081 | 3279 |
\<close> |
53617 | 3280 |
*) |
52794 | 3281 |
|
3282 |
||
62081 | 3283 |
section \<open> Selecting Plugins |
3284 |
\label{sec:selecting-plugins} \<close> |
|
3285 |
||
3286 |
text \<open> |
|
58190 | 3287 |
Plugins extend the (co)datatype package to interoperate with other Isabelle |
58192 | 3288 |
packages and tools, such as the code generator, Transfer, Lifting, and |
3289 |
Quickcheck. They can be enabled or disabled individually using the |
|
58310 | 3290 |
@{syntax plugins} option to the commands @{command datatype}, |
59300 | 3291 |
@{command primrec}, @{command codatatype}, @{command primcorec}, |
3292 |
@{command primcorecursive}, @{command bnf}, @{command bnf_axiomatization}, and |
|
3293 |
@{command free_constructors}. For example: |
|
62081 | 3294 |
\<close> |
58190 | 3295 |
|
58659
6c9821c32dd5
Local_Interpretation is superseded by Plugin with formal Plugin_Name management, avoiding undeclared strings;
wenzelm
parents:
58620
diff
changeset
|
3296 |
datatype (plugins del: code "quickcheck") color = Red | Black |
58192 | 3297 |
|
62081 | 3298 |
text \<open> |
61788 | 3299 |
Beyond the standard plugins, the \emph{Archive of Formal Proofs} includes a |
3300 |
\keyw{derive} command that derives class instances of datatypes |
|
3301 |
@{cite "sternagel-thiemann-2015"}. |
|
62081 | 3302 |
\<close> |
3303 |
||
3304 |
subsection \<open> Code Generator |
|
3305 |
\label{ssec:code-generator} \<close> |
|
3306 |
||
3307 |
text \<open> |
|
59299 | 3308 |
The \hthm{code} plugin registers freely generated types, including |
3309 |
(co)datatypes, and (co)recursive functions for code generation. No distinction |
|
3310 |
is made between datatypes and codatatypes. This means that for target languages |
|
3311 |
with a strict evaluation strategy (e.g., Standard ML), programs that attempt to |
|
3312 |
produce infinite codatatype values will not terminate. |
|
3313 |
||
3314 |
For types, the plugin derives the following properties: |
|
58244 | 3315 |
|
3316 |
\begin{indentblock} |
|
3317 |
\begin{description} |
|
3318 |
||
3319 |
\item[@{text "t."}\hthm{eq.refl} @{text "[code nbe]"}\rm:] ~ \\ |
|
3320 |
@{thm list.eq.refl[no_vars]} |
|
3321 |
||
3322 |
\item[@{text "t."}\hthm{eq.simps} @{text "[code]"}\rm:] ~ \\ |
|
3323 |
@{thm list.eq.simps(1)[no_vars]} \\ |
|
3324 |
@{thm list.eq.simps(2)[no_vars]} \\ |
|
3325 |
@{thm list.eq.simps(3)[no_vars]} \\ |
|
3326 |
@{thm list.eq.simps(4)[no_vars]} \\ |
|
3327 |
@{thm list.eq.simps(5)[no_vars]} \\ |
|
3328 |
@{thm list.eq.simps(6)[no_vars]} |
|
3329 |
||
3330 |
\end{description} |
|
3331 |
\end{indentblock} |
|
58509 | 3332 |
|
3333 |
In addition, the plugin sets the @{text "[code]"} attribute on a number of |
|
59299 | 3334 |
properties of freely generated types and of (co)recursive functions, as |
3335 |
documented in Sections \ref{ssec:datatype-generated-theorems}, |
|
3336 |
\ref{ssec:primrec-generated-theorems}, \ref{ssec:codatatype-generated-theorems}, |
|
3337 |
and~\ref{ssec:primcorec-generated-theorems}. |
|
62081 | 3338 |
\<close> |
3339 |
||
3340 |
||
3341 |
subsection \<open> Size |
|
3342 |
\label{ssec:size} \<close> |
|
3343 |
||
3344 |
text \<open> |
|
61787 | 3345 |
For each datatype @{text t}, the \hthm{size} plugin generates a generic size |
58190 | 3346 |
function @{text "t.size_t"} as well as a specific instance |
61787 | 3347 |
@{text "size :: t \<Rightarrow> nat"} belonging to the @{text size} type class. The |
3348 |
\keyw{fun} command relies on @{const size} to prove termination of recursive |
|
3349 |
functions on datatypes. |
|
58190 | 3350 |
|
3351 |
The plugin derives the following properties: |
|
3352 |
||
3353 |
\begin{indentblock} |
|
3354 |
\begin{description} |
|
3355 |
||
3356 |
\item[@{text "t."}\hthm{size} @{text "[simp, code]"}\rm:] ~ \\ |
|
3357 |
@{thm list.size(1)[no_vars]} \\ |
|
3358 |
@{thm list.size(2)[no_vars]} \\ |
|
3359 |
@{thm list.size(3)[no_vars]} \\ |
|
3360 |
@{thm list.size(4)[no_vars]} |
|
3361 |
||
58737 | 3362 |
\item[@{text "t."}\hthm{size_gen}\rm:] ~ \\ |
3363 |
@{thm list.size_gen(1)[no_vars]} \\ |
|
3364 |
@{thm list.size_gen(2)[no_vars]} |
|
3365 |
||
58739 | 3366 |
\item[@{text "t."}\hthm{size_gen_o_map}\rm:] ~ \\ |
3367 |
@{thm list.size_gen_o_map[no_vars]} |
|
58190 | 3368 |
|
58914 | 3369 |
\item[@{text "t."}\hthm{size_neq}\rm:] ~ \\ |
3370 |
This property is missing for @{typ "'a list"}. If the @{term size} function |
|
60134 | 3371 |
always evaluates to a non-zero value, this theorem has the form |
58914 | 3372 |
@{prop "\<not> size x = 0"}. |
3373 |
||
58190 | 3374 |
\end{description} |
3375 |
\end{indentblock} |
|
61787 | 3376 |
|
3377 |
The @{text "t.size"} and @{text "t.size_t"} functions generated for datatypes |
|
3378 |
defined by nested recursion through a datatype @{text u} depend on |
|
3379 |
@{text "u.size_u"}. |
|
3380 |
||
3381 |
If the recursion is through a non-datatype @{text u} with type arguments |
|
3382 |
@{text "'a\<^sub>1, \<dots>, 'a\<^sub>m"}, by default @{text u} values are given a size of 0. This |
|
3383 |
can be improved upon by registering a custom size function of type |
|
3384 |
@{text "('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat"} using |
|
61788 | 3385 |
the ML function @{ML BNF_LFP_Size.register_size} or |
3386 |
@{ML BNF_LFP_Size.register_size_global}. See theory |
|
61787 | 3387 |
@{file "~~/src/HOL/Library/Multiset.thy"} for an example. |
62081 | 3388 |
\<close> |
3389 |
||
3390 |
||
3391 |
subsection \<open> Transfer |
|
3392 |
\label{ssec:transfer} \<close> |
|
3393 |
||
3394 |
text \<open> |
|
58192 | 3395 |
For each (co)datatype with live type arguments and each manually registered BNF, |
58245 | 3396 |
the \hthm{transfer} plugin generates a predicator @{text "t.pred_t"} and |
58244 | 3397 |
properties that guide the Transfer tool. |
3398 |
||
61349 | 3399 |
For types with at least one live type argument and \emph{no dead type |
3400 |
arguments}, the plugin derives the following properties: |
|
58244 | 3401 |
|
3402 |
\begin{indentblock} |
|
3403 |
\begin{description} |
|
3404 |
||
3405 |
\item[@{text "t."}\hthm{Domainp_rel} @{text "[relator_domain]"}\rm:] ~ \\ |
|
3406 |
@{thm list.Domainp_rel[no_vars]} |
|
3407 |
||
3408 |
\item[@{text "t."}\hthm{pred_inject} @{text "[simp]"}\rm:] ~ \\ |
|
3409 |
@{thm list.pred_inject(1)[no_vars]} \\ |
|
59579 | 3410 |
@{thm list.pred_inject(2)[no_vars]} \\ |
3411 |
This property is generated only for (co)datatypes. |
|
58244 | 3412 |
|
58374
1b4d31b7bd10
fixed attribute name in docs (thanks to Andreas Lochbihler)
blanchet
parents:
58357
diff
changeset
|
3413 |
\item[@{text "t."}\hthm{left_total_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
58244 | 3414 |
@{thm list.left_total_rel[no_vars]} |
3415 |
||
58374
1b4d31b7bd10
fixed attribute name in docs (thanks to Andreas Lochbihler)
blanchet
parents:
58357
diff
changeset
|
3416 |
\item[@{text "t."}\hthm{left_unique_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
58244 | 3417 |
@{thm list.left_unique_rel[no_vars]} |
3418 |
||
58374
1b4d31b7bd10
fixed attribute name in docs (thanks to Andreas Lochbihler)
blanchet
parents:
58357
diff
changeset
|
3419 |
\item[@{text "t."}\hthm{right_total_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
58244 | 3420 |
@{thm list.right_total_rel[no_vars]} |
3421 |
||
58374
1b4d31b7bd10
fixed attribute name in docs (thanks to Andreas Lochbihler)
blanchet
parents:
58357
diff
changeset
|
3422 |
\item[@{text "t."}\hthm{right_unique_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
58244 | 3423 |
@{thm list.right_unique_rel[no_vars]} |
3424 |
||
58374
1b4d31b7bd10
fixed attribute name in docs (thanks to Andreas Lochbihler)
blanchet
parents:
58357
diff
changeset
|
3425 |
\item[@{text "t."}\hthm{bi_total_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
58244 | 3426 |
@{thm list.bi_total_rel[no_vars]} |
3427 |
||
58374
1b4d31b7bd10
fixed attribute name in docs (thanks to Andreas Lochbihler)
blanchet
parents:
58357
diff
changeset
|
3428 |
\item[@{text "t."}\hthm{bi_unique_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
58244 | 3429 |
@{thm list.bi_unique_rel[no_vars]} |
3430 |
||
3431 |
\end{description} |
|
3432 |
\end{indentblock} |
|
59282 | 3433 |
|
61349 | 3434 |
For (co)datatypes with at least one live type argument, the plugin sets the |
3435 |
@{text "[transfer_rule]"} attribute on the following (co)datatypes properties: |
|
61788 | 3436 |
@{text "t.case_"}\allowbreak @{text "transfer"}, |
3437 |
@{text "t.sel_"}\allowbreak @{text "transfer"}, |
|
3438 |
@{text "t.ctr_"}\allowbreak @{text "transfer"}, |
|
3439 |
@{text "t.disc_"}\allowbreak @{text "transfer"}, |
|
3440 |
@{text "t.rec_"}\allowbreak @{text "transfer"}, and |
|
3441 |
@{text "t.corec_"}\allowbreak @{text "transfer"}. |
|
3442 |
For (co)datatypes that further have \emph{no dead type arguments}, the plugin |
|
3443 |
sets @{text "[transfer_rule]"} on |
|
3444 |
@{text "t.set_"}\allowbreak @{text "transfer"}, |
|
3445 |
@{text "t.map_"}\allowbreak @{text "transfer"}, and |
|
3446 |
@{text "t.rel_"}\allowbreak @{text "transfer"}. |
|
59579 | 3447 |
|
59282 | 3448 |
For @{command primrec}, @{command primcorec}, and @{command primcorecursive}, |
59579 | 3449 |
the plugin implements the generation of the @{text "f.transfer"} property, |
3450 |
conditioned by the @{text transfer} option, and sets the |
|
3451 |
@{text "[transfer_rule]"} attribute on these. |
|
62081 | 3452 |
\<close> |
3453 |
||
3454 |
||
3455 |
subsection \<open> Lifting |
|
3456 |
\label{ssec:lifting} \<close> |
|
3457 |
||
3458 |
text \<open> |
|
59721 | 3459 |
For each (co)datatype and each manually registered BNF with at least one live |
61349 | 3460 |
type argument \emph{and no dead type arguments}, the \hthm{lifting} plugin |
3461 |
generates properties and attributes that guide the Lifting tool. |
|
58244 | 3462 |
|
3463 |
The plugin derives the following property: |
|
3464 |
||
3465 |
\begin{indentblock} |
|
3466 |
\begin{description} |
|
3467 |
||
3468 |
\item[@{text "t."}\hthm{Quotient} @{text "[quot_map]"}\rm:] ~ \\ |
|
3469 |
@{thm list.Quotient[no_vars]} |
|
3470 |
||
3471 |
\end{description} |
|
3472 |
\end{indentblock} |
|
3473 |
||
61349 | 3474 |
In addition, the plugin sets the @{text "[relator_eq]"} attribute on a |
62330 | 3475 |
variant of the @{text t.rel_eq_onp} property, the @{text "[relator_mono]"} |
3476 |
attribute on @{text t.rel_mono}, and the @{text "[relator_distr]"} attribute |
|
3477 |
on @{text t.rel_compp}. |
|
62081 | 3478 |
\<close> |
3479 |
||
3480 |
||
3481 |
subsection \<open> Quickcheck |
|
3482 |
\label{ssec:quickcheck} \<close> |
|
3483 |
||
3484 |
text \<open> |
|
59280 | 3485 |
The integration of datatypes with Quickcheck is accomplished by the |
59282 | 3486 |
\hthm{quick\-check} plugin. It combines a number of subplugins that instantiate |
59280 | 3487 |
specific type classes. The subplugins can be enabled or disabled individually. |
3488 |
They are listed below: |
|
58245 | 3489 |
|
3490 |
\begin{indentblock} |
|
3491 |
\hthm{quickcheck_random} \\ |
|
3492 |
\hthm{quickcheck_exhaustive} \\ |
|
3493 |
\hthm{quickcheck_bounded_forall} \\ |
|
3494 |
\hthm{quickcheck_full_exhaustive} \\ |
|
3495 |
\hthm{quickcheck_narrowing} |
|
3496 |
\end{indentblock} |
|
62081 | 3497 |
\<close> |
3498 |
||
3499 |
||
3500 |
subsection \<open> Program Extraction |
|
3501 |
\label{ssec:program-extraction} \<close> |
|
3502 |
||
3503 |
text \<open> |
|
58278 | 3504 |
The \hthm{extraction} plugin provides realizers for induction and case analysis, |
3505 |
to enable program extraction from proofs involving datatypes. This functionality |
|
58395 | 3506 |
is only available with full proof objects, i.e., with the \emph{HOL-Proofs} |
58278 | 3507 |
session. |
62081 | 3508 |
\<close> |
3509 |
||
3510 |
||
3511 |
section \<open> Known Bugs and Limitations |
|
3512 |
\label{sec:known-bugs-and-limitations} \<close> |
|
3513 |
||
3514 |
text \<open> |
|
58395 | 3515 |
This section lists the known bugs and limitations in the (co)datatype package at |
3516 |
the time of this writing. Many of them are expected to be addressed in future |
|
3517 |
releases. |
|
3518 |
||
3519 |
\begin{enumerate} |
|
3520 |
\setlength{\itemsep}{0pt} |
|
3521 |
||
3522 |
\item |
|
62317 | 3523 |
\emph{Defining mutually (co)recursive (co)datatypes can be slow.} Fortunately, |
58395 | 3524 |
it is always possible to recast mutual specifications to nested ones, which are |
3525 |
processed more efficiently. |
|
3526 |
||
3527 |
\item |
|
60736 | 3528 |
\emph{Locally fixed types and terms cannot be used in type specifications.} |
3529 |
The limitation on types can be circumvented by adding type arguments to the local |
|
58395 | 3530 |
(co)datatypes to abstract over the locally fixed types. |
3531 |
||
3532 |
\item |
|
3533 |
\emph{The \emph{\keyw{primcorec}} command does not allow user-specified names and |
|
3534 |
attributes next to the entered formulas.} The less convenient syntax, using the |
|
3535 |
\keyw{lemmas} command, is available as an alternative. |
|
3536 |
||
3537 |
\item |
|
62317 | 3538 |
\emph{The \emph{\keyw{primcorec}} command does not allow corecursion under |
3539 |
@{text "case"}--@{text "of"} for datatypes that are defined without |
|
3540 |
discriminators and selectors. |
|
3541 |
||
3542 |
\item |
|
58395 | 3543 |
\emph{There is no way to use an overloaded constant from a syntactic type |
3544 |
class, such as @{text 0}, as a constructor.} |
|
3545 |
||
3546 |
\item |
|
3547 |
\emph{There is no way to register the same type as both a datatype and a |
|
3548 |
codatatype.} This affects types such as the extended natural numbers, for which |
|
3549 |
both views would make sense (for a different set of constructors). |
|
3550 |
||
3551 |
\item |
|
3552 |
\emph{The names of variables are often suboptimal in the properties generated by |
|
3553 |
the package.} |
|
3554 |
||
60146 | 3555 |
\item |
3556 |
\emph{The compatibility layer sometimes produces induction principles with a |
|
61788 | 3557 |
slightly different ordering of the premises than the old package.} |
60146 | 3558 |
|
58395 | 3559 |
\end{enumerate} |
62081 | 3560 |
\<close> |
3561 |
||
3562 |
||
3563 |
text \<open> |
|
53863
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
3564 |
\section*{Acknowledgment} |
c7364dca96f2
textual improvements following Christian Sternagel's feedback
blanchet
parents:
53857
diff
changeset
|
3565 |
|
53749
b37db925b663
adapted primcorec documentation to reflect the three views
blanchet
parents:
53748
diff
changeset
|
3566 |
Tobias Nipkow and Makarius Wenzel encouraged us to implement the new |
53617 | 3567 |
(co)datatype package. Andreas Lochbihler provided lots of comments on earlier |
56655 | 3568 |
versions of the package, especially on the coinductive part. Brian Huffman |
58245 | 3569 |
suggested major simplifications to the internal constructions. Ond\v{r}ej |
3570 |
Kun\v{c}ar implemented the @{text transfer} and @{text lifting} plugins. |
|
60137 | 3571 |
Christian Sternagel and Ren\'e Thiemann ported the \keyw{derive} command |
62081 | 3572 |
from the \emph{Archive of Formal Proofs} to the new datatypes. Gerwin Klein and |
3573 |
Lars Noschinski implemented the @{command simps_of_case} and @{command |
|
3574 |
case_of_simps} commands. Florian Haftmann, Christian Urban, and Makarius |
|
3575 |
Wenzel provided general advice on Isabelle and package writing. Stefan Milius |
|
3576 |
and Lutz Schr\"oder found an elegant proof that eliminated one of the BNF |
|
3577 |
proof obligations. Mamoun Filali-Amine, Gerwin Klein, Andreas Lochbihler, |
|
3578 |
Tobias Nipkow, and Christian Sternagel suggested many textual improvements to |
|
3579 |
this tutorial. |
|
3580 |
\<close> |
|
53617 | 3581 |
|
52792 | 3582 |
end |