changeset 69505 | cc2d676d5395 |
parent 68484 | 59793df7f853 |
child 69597 | ff784d5a5bfb |
69504:bda7527ccf05 | 69505:cc2d676d5395 |
---|---|
83 The package, like its predecessor, fully adheres to the LCF philosophy |
83 The package, like its predecessor, fully adheres to the LCF philosophy |
84 @{cite mgordon79}: The characteristic theorems associated with the specified |
84 @{cite mgordon79}: The characteristic theorems associated with the specified |
85 (co)datatypes are derived rather than introduced axiomatically.% |
85 (co)datatypes are derived rather than introduced axiomatically.% |
86 \footnote{However, some of the |
86 \footnote{However, some of the |
87 internal constructions and most of the internal proof obligations are omitted |
87 internal constructions and most of the internal proof obligations are omitted |
88 if the @{text quick_and_dirty} option is enabled.} |
88 if the \<open>quick_and_dirty\<close> option is enabled.} |
89 The package is described in a number of scientific papers |
89 The package is described in a number of scientific papers |
90 @{cite "traytel-et-al-2012" and "blanchette-et-al-2014-impl" and |
90 @{cite "traytel-et-al-2012" and "blanchette-et-al-2014-impl" and |
91 "panny-et-al-2014" and "blanchette-et-al-2015-wit"}. |
91 "panny-et-al-2014" and "blanchette-et-al-2015-wit"}. |
92 The central notion is that of a \emph{bounded natural functor} (BNF)---a |
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. |
93 well-behaved type constructor for which nested (co)recursion is supported. |
192 (*>*) |
192 (*>*) |
193 datatype 'a option = None | Some 'a |
193 datatype 'a option = None | Some 'a |
194 |
194 |
195 text \<open> |
195 text \<open> |
196 \noindent |
196 \noindent |
197 The constructors are @{text "None :: 'a option"} and |
197 The constructors are \<open>None :: 'a option\<close> and |
198 @{text "Some :: 'a \<Rightarrow> 'a option"}. |
198 \<open>Some :: 'a \<Rightarrow> 'a option\<close>. |
199 |
199 |
200 The next example has three type parameters: |
200 The next example has three type parameters: |
201 \<close> |
201 \<close> |
202 |
202 |
203 datatype ('a, 'b, 'c) triple = Triple 'a 'b 'c |
203 datatype ('a, 'b, 'c) triple = Triple 'a 'b 'c |
204 |
204 |
205 text \<open> |
205 text \<open> |
206 \noindent |
206 \noindent |
207 The constructor is |
207 The constructor is |
208 @{text "Triple :: 'a \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> ('a, 'b, 'c) triple"}. |
208 \<open>Triple :: 'a \<Rightarrow> 'b \<Rightarrow> 'c \<Rightarrow> ('a, 'b, 'c) triple\<close>. |
209 Unlike in Standard ML, curried constructors are supported. The uncurried variant |
209 Unlike in Standard ML, curried constructors are supported. The uncurried variant |
210 is also possible: |
210 is also possible: |
211 \<close> |
211 \<close> |
212 |
212 |
213 datatype ('a, 'b, 'c) triple\<^sub>u = Triple\<^sub>u "'a * 'b * 'c" |
213 datatype ('a, 'b, 'c) triple\<^sub>u = Triple\<^sub>u "'a * 'b * 'c" |
284 datatype 'a wrong = W1 | W2 (*<*)'a |
284 datatype 'a wrong = W1 | W2 (*<*)'a |
285 typ (*>*)"'a wrong \<Rightarrow> 'a" |
285 typ (*>*)"'a wrong \<Rightarrow> 'a" |
286 |
286 |
287 text \<open> |
287 text \<open> |
288 \noindent |
288 \noindent |
289 The issue is that the function arrow @{text "\<Rightarrow>"} allows recursion |
289 The issue is that the function arrow \<open>\<Rightarrow>\<close> allows recursion |
290 only through its right-hand side. This issue is inherited by polymorphic |
290 only through its right-hand side. This issue is inherited by polymorphic |
291 datatypes defined in terms of~@{text "\<Rightarrow>"}: |
291 datatypes defined in terms of~\<open>\<Rightarrow>\<close>: |
292 \<close> |
292 \<close> |
293 |
293 |
294 datatype ('a, 'b) fun_copy = Fun "'a \<Rightarrow> 'b" |
294 datatype ('a, 'b) fun_copy = Fun "'a \<Rightarrow> 'b" |
295 datatype 'a also_wrong = W1 | W2 (*<*)'a |
295 datatype 'a also_wrong = W1 | W2 (*<*)'a |
296 typ (*>*)"('a also_wrong, 'a) fun_copy" |
296 typ (*>*)"('a also_wrong, 'a) fun_copy" |
309 |
309 |
310 datatype hfset = HFSet "hfset fset" |
310 datatype hfset = HFSet "hfset fset" |
311 |
311 |
312 text \<open> |
312 text \<open> |
313 \noindent |
313 \noindent |
314 In general, type constructors @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
314 In general, type constructors \<open>('a\<^sub>1, \<dots>, 'a\<^sub>m) t\<close> |
315 allow recursion on a subset of their type arguments @{text 'a\<^sub>1}, \ldots, |
315 allow recursion on a subset of their type arguments \<open>'a\<^sub>1\<close>, \ldots, |
316 @{text 'a\<^sub>m}. These type arguments are called \emph{live}; the remaining |
316 \<open>'a\<^sub>m\<close>. These type arguments are called \emph{live}; the remaining |
317 type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and |
317 type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and |
318 @{typ "('a, 'b) fun_copy"}, the type variable @{typ 'a} is dead and |
318 @{typ "('a, 'b) fun_copy"}, the type variable @{typ 'a} is dead and |
319 @{typ 'b} is live. |
319 @{typ 'b} is live. |
320 |
320 |
321 Type constructors must be registered as BNFs to have live arguments. This is |
321 Type constructors must be registered as BNFs to have live arguments. This is |
343 |
343 |
344 text \<open> |
344 text \<open> |
345 The @{command datatype} command introduces various constants in addition to |
345 The @{command datatype} command introduces various constants in addition to |
346 the constructors. With each datatype are associated set functions, a map |
346 the constructors. With each datatype are associated set functions, a map |
347 function, a predicator, a relator, discriminators, and selectors, all of which can be given |
347 function, a predicator, a relator, discriminators, and selectors, all of which can be given |
348 custom names. In the example below, the familiar names @{text null}, @{text hd}, |
348 custom names. In the example below, the familiar names \<open>null\<close>, \<open>hd\<close>, |
349 @{text tl}, @{text set}, @{text map}, and @{text list_all2} override the |
349 \<open>tl\<close>, \<open>set\<close>, \<open>map\<close>, and \<open>list_all2\<close> override the |
350 default names @{text is_Nil}, @{text un_Cons1}, @{text un_Cons2}, |
350 default names \<open>is_Nil\<close>, \<open>un_Cons1\<close>, \<open>un_Cons2\<close>, |
351 @{text set_list}, @{text map_list}, and @{text rel_list}: |
351 \<open>set_list\<close>, \<open>map_list\<close>, and \<open>rel_list\<close>: |
352 \<close> |
352 \<close> |
353 |
353 |
354 (*<*) |
354 (*<*) |
355 no_translations |
355 no_translations |
356 "[x, xs]" == "x # [xs]" |
356 "[x, xs]" == "x # [xs]" |
382 |
382 |
383 \medskip |
383 \medskip |
384 |
384 |
385 \begin{tabular}{@ {}ll@ {}} |
385 \begin{tabular}{@ {}ll@ {}} |
386 Constructors: & |
386 Constructors: & |
387 @{text "Nil :: 'a list"} \\ |
387 \<open>Nil :: 'a list\<close> \\ |
388 & |
388 & |
389 @{text "Cons :: 'a \<Rightarrow> 'a list \<Rightarrow> 'a list"} \\ |
389 \<open>Cons :: 'a \<Rightarrow> 'a list \<Rightarrow> 'a list\<close> \\ |
390 Discriminator: & |
390 Discriminator: & |
391 @{text "null :: 'a list \<Rightarrow> bool"} \\ |
391 \<open>null :: 'a list \<Rightarrow> bool\<close> \\ |
392 Selectors: & |
392 Selectors: & |
393 @{text "hd :: 'a list \<Rightarrow> 'a"} \\ |
393 \<open>hd :: 'a list \<Rightarrow> 'a\<close> \\ |
394 & |
394 & |
395 @{text "tl :: 'a list \<Rightarrow> 'a list"} \\ |
395 \<open>tl :: 'a list \<Rightarrow> 'a list\<close> \\ |
396 Set function: & |
396 Set function: & |
397 @{text "set :: 'a list \<Rightarrow> 'a set"} \\ |
397 \<open>set :: 'a list \<Rightarrow> 'a set\<close> \\ |
398 Map function: & |
398 Map function: & |
399 @{text "map :: ('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list"} \\ |
399 \<open>map :: ('a \<Rightarrow> 'b) \<Rightarrow> 'a list \<Rightarrow> 'b list\<close> \\ |
400 Relator: & |
400 Relator: & |
401 @{text "list_all2 :: ('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> 'a list \<Rightarrow> 'b list \<Rightarrow> bool"} |
401 \<open>list_all2 :: ('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> 'a list \<Rightarrow> 'b list \<Rightarrow> bool\<close> |
402 \end{tabular} |
402 \end{tabular} |
403 |
403 |
404 \medskip |
404 \medskip |
405 |
405 |
406 The discriminator @{const null} and the selectors @{const hd} and @{const tl} |
406 The discriminator @{const null} and the selectors @{const hd} and @{const tl} |
464 subsubsection \<open>\keyw{datatype} |
464 subsubsection \<open>\keyw{datatype} |
465 \label{sssec:datatype}\<close> |
465 \label{sssec:datatype}\<close> |
466 |
466 |
467 text \<open> |
467 text \<open> |
468 \begin{matharray}{rcl} |
468 \begin{matharray}{rcl} |
469 @{command_def "datatype"} & : & @{text "local_theory \<rightarrow> local_theory"} |
469 @{command_def "datatype"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
470 \end{matharray} |
470 \end{matharray} |
471 |
471 |
472 @{rail \<open> |
472 @{rail \<open> |
473 @@{command datatype} target? @{syntax dt_options}? @{syntax dt_spec} |
473 @@{command datatype} target? @{syntax dt_options}? @{syntax dt_spec} |
474 ; |
474 ; |
487 \noindent |
487 \noindent |
488 The @{command datatype} command introduces a set of mutually recursive |
488 The @{command datatype} command introduces a set of mutually recursive |
489 datatypes specified by their constructors. |
489 datatypes specified by their constructors. |
490 |
490 |
491 The syntactic entity \synt{target} can be used to specify a local |
491 The syntactic entity \synt{target} can be used to specify a local |
492 context (e.g., @{text "(in linorder)"} @{cite "isabelle-isar-ref"}), |
492 context (e.g., \<open>(in linorder)\<close> @{cite "isabelle-isar-ref"}), |
493 and \synt{prop} denotes a HOL proposition. |
493 and \synt{prop} denotes a HOL proposition. |
494 |
494 |
495 The optional target is optionally followed by a combination of the following |
495 The optional target is optionally followed by a combination of the following |
496 options: |
496 options: |
497 |
497 |
498 \begin{itemize} |
498 \begin{itemize} |
499 \setlength{\itemsep}{0pt} |
499 \setlength{\itemsep}{0pt} |
500 |
500 |
501 \item |
501 \item |
502 The @{text plugins} option indicates which plugins should be enabled |
502 The \<open>plugins\<close> option indicates which plugins should be enabled |
503 (@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
503 (\<open>only\<close>) or disabled (\<open>del\<close>). By default, all plugins are enabled. |
504 |
504 |
505 \item |
505 \item |
506 The @{text "discs_sels"} option indicates that discriminators and selectors |
506 The \<open>discs_sels\<close> option indicates that discriminators and selectors |
507 should be generated. The option is implicitly enabled if names are specified for |
507 should be generated. The option is implicitly enabled if names are specified for |
508 discriminators or selectors. |
508 discriminators or selectors. |
509 \end{itemize} |
509 \end{itemize} |
510 |
510 |
511 The optional \keyw{where} clause specifies default values for selectors. |
511 The optional \keyw{where} clause specifies default values for selectors. |
512 Each proposition must be an equation of the form |
512 Each proposition must be an equation of the form |
513 @{text "un_D (C \<dots>) = \<dots>"}, where @{text C} is a constructor and |
513 \<open>un_D (C \<dots>) = \<dots>\<close>, where \<open>C\<close> is a constructor and |
514 @{text un_D} is a selector. |
514 \<open>un_D\<close> is a selector. |
515 |
515 |
516 The left-hand sides of the datatype equations specify the name of the type to |
516 The left-hand sides of the datatype equations specify the name of the type to |
517 define, its type parameters, and additional information: |
517 define, its type parameters, and additional information: |
518 |
518 |
519 @{rail \<open> |
519 @{rail \<open> |
528 The syntactic entity \synt{name} denotes an identifier, \synt{mixfix} denotes |
528 The syntactic entity \synt{name} denotes an identifier, \synt{mixfix} denotes |
529 the usual parenthesized mixfix notation, and \synt{typefree} denotes fixed type |
529 the usual parenthesized mixfix notation, and \synt{typefree} denotes fixed type |
530 variable (@{typ 'a}, @{typ 'b}, \ldots) @{cite "isabelle-isar-ref"}. |
530 variable (@{typ 'a}, @{typ 'b}, \ldots) @{cite "isabelle-isar-ref"}. |
531 |
531 |
532 The optional names preceding the type variables allow to override the default |
532 The optional names preceding the type variables allow to override the default |
533 names of the set functions (@{text set\<^sub>1_t}, \ldots, @{text set\<^sub>m_t}). Type |
533 names of the set functions (\<open>set\<^sub>1_t\<close>, \ldots, \<open>set\<^sub>m_t\<close>). Type |
534 arguments can be marked as dead by entering @{text dead} in front of the |
534 arguments can be marked as dead by entering \<open>dead\<close> in front of the |
535 type variable (e.g., @{text "(dead 'a)"}); otherwise, they are live or dead |
535 type variable (e.g., \<open>(dead 'a)\<close>); otherwise, they are live or dead |
536 (and a set function is generated or not) depending on where they occur in the |
536 (and a set function is generated or not) depending on where they occur in the |
537 right-hand sides of the definition. Declaring a type argument as dead can speed |
537 right-hand sides of the definition. Declaring a type argument as dead can speed |
538 up the type definition but will prevent any later (co)recursion through that |
538 up the type definition but will prevent any later (co)recursion through that |
539 type argument. |
539 type argument. |
540 |
540 |
549 |
549 |
550 \noindent |
550 \noindent |
551 The main constituents of a constructor specification are the name of the |
551 The main constituents of a constructor specification are the name of the |
552 constructor and the list of its argument types. An optional discriminator name |
552 constructor and the list of its argument types. An optional discriminator name |
553 can be supplied at the front. If discriminators are enabled (cf.\ the |
553 can be supplied at the front. If discriminators are enabled (cf.\ the |
554 @{text "discs_sels"} option) but no name is supplied, the default is |
554 \<open>discs_sels\<close> option) but no name is supplied, the default is |
555 @{text "\<lambda>x. x = C\<^sub>j"} for nullary constructors and |
555 \<open>\<lambda>x. x = C\<^sub>j\<close> for nullary constructors and |
556 @{text t.is_C\<^sub>j} otherwise. |
556 \<open>t.is_C\<^sub>j\<close> otherwise. |
557 |
557 |
558 @{rail \<open> |
558 @{rail \<open> |
559 @{syntax_def dt_ctor_arg}: type | '(' name ':' type ')' |
559 @{syntax_def dt_ctor_arg}: type | '(' name ':' type ')' |
560 \<close>} |
560 \<close>} |
561 |
561 |
565 The syntactic entity \synt{type} denotes a HOL type @{cite "isabelle-isar-ref"}. |
565 The syntactic entity \synt{type} denotes a HOL type @{cite "isabelle-isar-ref"}. |
566 |
566 |
567 In addition to the type of a constructor argument, it is possible to specify a |
567 In addition to the type of a constructor argument, it is possible to specify a |
568 name for the corresponding selector. The same selector name can be reused for |
568 name for the corresponding selector. The same selector name can be reused for |
569 arguments to several constructors as long as the arguments share the same type. |
569 arguments to several constructors as long as the arguments share the same type. |
570 If selectors are enabled (cf.\ the @{text "discs_sels"} option) but no name is |
570 If selectors are enabled (cf.\ the \<open>discs_sels\<close> option) but no name is |
571 supplied, the default name is @{text un_C\<^sub>ji}. |
571 supplied, the default name is \<open>un_C\<^sub>ji\<close>. |
572 \<close> |
572 \<close> |
573 |
573 |
574 |
574 |
575 subsubsection \<open>\keyw{datatype_compat} |
575 subsubsection \<open>\keyw{datatype_compat} |
576 \label{sssec:datatype-compat}\<close> |
576 \label{sssec:datatype-compat}\<close> |
577 |
577 |
578 text \<open> |
578 text \<open> |
579 \begin{matharray}{rcl} |
579 \begin{matharray}{rcl} |
580 @{command_def "datatype_compat"} & : & @{text "local_theory \<rightarrow> local_theory"} |
580 @{command_def "datatype_compat"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
581 \end{matharray} |
581 \end{matharray} |
582 |
582 |
583 @{rail \<open> |
583 @{rail \<open> |
584 @@{command datatype_compat} (name +) |
584 @@{command datatype_compat} (name +) |
585 \<close>} |
585 \<close>} |
607 |
607 |
608 \begin{itemize} |
608 \begin{itemize} |
609 \setlength{\itemsep}{0pt} |
609 \setlength{\itemsep}{0pt} |
610 |
610 |
611 \item The old-style, nested-as-mutual induction rule and recursor theorems are |
611 \item The old-style, nested-as-mutual induction rule and recursor theorems are |
612 generated under their usual names but with ``@{text "compat_"}'' prefixed |
612 generated under their usual names but with ``\<open>compat_\<close>'' prefixed |
613 (e.g., @{text compat_tree.induct}, @{text compat_tree.inducts}, and |
613 (e.g., \<open>compat_tree.induct\<close>, \<open>compat_tree.inducts\<close>, and |
614 @{text compat_tree.rec}). These theorems should be identical to the ones |
614 \<open>compat_tree.rec\<close>). These theorems should be identical to the ones |
615 generated by the old datatype package, \emph{up to the order of the |
615 generated by the old datatype package, \emph{up to the order of the |
616 premises}---meaning that the subgoals generated by the @{text induct} or |
616 premises}---meaning that the subgoals generated by the \<open>induct\<close> or |
617 @{text induction} method may be in a different order than before. |
617 \<open>induction\<close> method may be in a different order than before. |
618 |
618 |
619 \item All types through which recursion takes place must be new-style datatypes |
619 \item All types through which recursion takes place must be new-style datatypes |
620 or the function type. |
620 or the function type. |
621 \end{itemize} |
621 \end{itemize} |
622 \<close> |
622 \<close> |
624 |
624 |
625 subsection \<open>Generated Constants |
625 subsection \<open>Generated Constants |
626 \label{ssec:datatype-generated-constants}\<close> |
626 \label{ssec:datatype-generated-constants}\<close> |
627 |
627 |
628 text \<open> |
628 text \<open> |
629 Given a datatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} with $m$ live type variables |
629 Given a datatype \<open>('a\<^sub>1, \<dots>, 'a\<^sub>m) t\<close> with $m$ live type variables |
630 and $n$ constructors @{text "t.C\<^sub>1"}, \ldots, @{text "t.C\<^sub>n"}, the following |
630 and $n$ constructors \<open>t.C\<^sub>1\<close>, \ldots, \<open>t.C\<^sub>n\<close>, the following |
631 auxiliary constants are introduced: |
631 auxiliary constants are introduced: |
632 |
632 |
633 \medskip |
633 \medskip |
634 |
634 |
635 \begin{tabular}{@ {}ll@ {}} |
635 \begin{tabular}{@ {}ll@ {}} |
636 Case combinator: & |
636 Case combinator: & |
637 @{text t.case_t} (rendered using the familiar @{text case}--@{text of} syntax) \\ |
637 \<open>t.case_t\<close> (rendered using the familiar \<open>case\<close>--\<open>of\<close> syntax) \\ |
638 Discriminators: & |
638 Discriminators: & |
639 @{text t.is_C\<^sub>1}$, \ldots, $@{text t.is_C\<^sub>n} \\ |
639 \<open>t.is_C\<^sub>1\<close>$, \ldots, $\<open>t.is_C\<^sub>n\<close> \\ |
640 Selectors: & |
640 Selectors: & |
641 @{text t.un_C\<^sub>11}$, \ldots, $@{text t.un_C\<^sub>1k\<^sub>1} \\ |
641 \<open>t.un_C\<^sub>11\<close>$, \ldots, $\<open>t.un_C\<^sub>1k\<^sub>1\<close> \\ |
642 & \quad\vdots \\ |
642 & \quad\vdots \\ |
643 & @{text t.un_C\<^sub>n1}$, \ldots, $@{text t.un_C\<^sub>nk\<^sub>n} \\ |
643 & \<open>t.un_C\<^sub>n1\<close>$, \ldots, $\<open>t.un_C\<^sub>nk\<^sub>n\<close> \\ |
644 Set functions: & |
644 Set functions: & |
645 @{text t.set\<^sub>1_t}, \ldots, @{text t.set\<^sub>m_t} \\ |
645 \<open>t.set\<^sub>1_t\<close>, \ldots, \<open>t.set\<^sub>m_t\<close> \\ |
646 Map function: & |
646 Map function: & |
647 @{text t.map_t} \\ |
647 \<open>t.map_t\<close> \\ |
648 Relator: & |
648 Relator: & |
649 @{text t.rel_t} \\ |
649 \<open>t.rel_t\<close> \\ |
650 Recursor: & |
650 Recursor: & |
651 @{text t.rec_t} |
651 \<open>t.rec_t\<close> |
652 \end{tabular} |
652 \end{tabular} |
653 |
653 |
654 \medskip |
654 \medskip |
655 |
655 |
656 \noindent |
656 \noindent |
657 The discriminators and selectors are generated only if the @{text "discs_sels"} |
657 The discriminators and selectors are generated only if the \<open>discs_sels\<close> |
658 option is enabled or if names are specified for discriminators or selectors. |
658 option is enabled or if names are specified for discriminators or selectors. |
659 The set functions, map function, predicator, and relator are generated only if $m > 0$. |
659 The set functions, map function, predicator, and relator are generated only if $m > 0$. |
660 |
660 |
661 In addition, some of the plugins introduce their own constants |
661 In addition, some of the plugins introduce their own constants |
662 (Section~\ref{sec:selecting-plugins}). The case combinator, discriminators, |
662 (Section~\ref{sec:selecting-plugins}). The case combinator, discriminators, |
663 and selectors are collectively called \emph{destructors}. The prefix |
663 and selectors are collectively called \emph{destructors}. The prefix |
664 ``@{text "t."}'' is an optional component of the names and is normally hidden. |
664 ``\<open>t.\<close>'' is an optional component of the names and is normally hidden. |
665 \<close> |
665 \<close> |
666 |
666 |
667 |
667 |
668 subsection \<open>Generated Theorems |
668 subsection \<open>Generated Theorems |
669 \label{ssec:datatype-generated-theorems}\<close> |
669 \label{ssec:datatype-generated-theorems}\<close> |
715 for @{typ "'a list"}: |
715 for @{typ "'a list"}: |
716 |
716 |
717 \begin{indentblock} |
717 \begin{indentblock} |
718 \begin{description} |
718 \begin{description} |
719 |
719 |
720 \item[@{text "t."}\hthm{inject} @{text "[iff, induct_simp]"}\rm:] ~ \\ |
720 \item[\<open>t.\<close>\hthm{inject} \<open>[iff, induct_simp]\<close>\rm:] ~ \\ |
721 @{thm list.inject[no_vars]} |
721 @{thm list.inject[no_vars]} |
722 |
722 |
723 \item[@{text "t."}\hthm{distinct} @{text "[simp, induct_simp]"}\rm:] ~ \\ |
723 \item[\<open>t.\<close>\hthm{distinct} \<open>[simp, induct_simp]\<close>\rm:] ~ \\ |
724 @{thm list.distinct(1)[no_vars]} \\ |
724 @{thm list.distinct(1)[no_vars]} \\ |
725 @{thm list.distinct(2)[no_vars]} |
725 @{thm list.distinct(2)[no_vars]} |
726 |
726 |
727 \item[@{text "t."}\hthm{exhaust} @{text "[cases t, case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
727 \item[\<open>t.\<close>\hthm{exhaust} \<open>[cases t, case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm:] ~ \\ |
728 @{thm list.exhaust[no_vars]} |
728 @{thm list.exhaust[no_vars]} |
729 |
729 |
730 \item[@{text "t."}\hthm{nchotomy}\rm:] ~ \\ |
730 \item[\<open>t.\<close>\hthm{nchotomy}\rm:] ~ \\ |
731 @{thm list.nchotomy[no_vars]} |
731 @{thm list.nchotomy[no_vars]} |
732 |
732 |
733 \end{description} |
733 \end{description} |
734 \end{indentblock} |
734 \end{indentblock} |
735 |
735 |
737 In addition, these nameless theorems are registered as safe elimination rules: |
737 In addition, these nameless theorems are registered as safe elimination rules: |
738 |
738 |
739 \begin{indentblock} |
739 \begin{indentblock} |
740 \begin{description} |
740 \begin{description} |
741 |
741 |
742 \item[@{text "t."}\hthm{distinct {\upshape[}THEN notE}@{text ", elim!"}\hthm{\upshape]}\rm:] ~ \\ |
742 \item[\<open>t.\<close>\hthm{distinct {\upshape[}THEN notE}\<open>, elim!\<close>\hthm{\upshape]}\rm:] ~ \\ |
743 @{thm list.distinct(1)[THEN notE, elim!, no_vars]} \\ |
743 @{thm list.distinct(1)[THEN notE, elim!, no_vars]} \\ |
744 @{thm list.distinct(2)[THEN notE, elim!, no_vars]} |
744 @{thm list.distinct(2)[THEN notE, elim!, no_vars]} |
745 |
745 |
746 \end{description} |
746 \end{description} |
747 \end{indentblock} |
747 \end{indentblock} |
750 The next subgroup is concerned with the case combinator: |
750 The next subgroup is concerned with the case combinator: |
751 |
751 |
752 \begin{indentblock} |
752 \begin{indentblock} |
753 \begin{description} |
753 \begin{description} |
754 |
754 |
755 \item[@{text "t."}\hthm{case} @{text "[simp, code]"}\rm:] ~ \\ |
755 \item[\<open>t.\<close>\hthm{case} \<open>[simp, code]\<close>\rm:] ~ \\ |
756 @{thm list.case(1)[no_vars]} \\ |
756 @{thm list.case(1)[no_vars]} \\ |
757 @{thm list.case(2)[no_vars]} \\ |
757 @{thm list.case(2)[no_vars]} \\ |
758 The @{text "[code]"} attribute is set by the @{text code} plugin |
758 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
759 (Section~\ref{ssec:code-generator}). |
759 (Section~\ref{ssec:code-generator}). |
760 |
760 |
761 \item[@{text "t."}\hthm{case_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
761 \item[\<open>t.\<close>\hthm{case_cong} \<open>[fundef_cong]\<close>\rm:] ~ \\ |
762 @{thm list.case_cong[no_vars]} |
762 @{thm list.case_cong[no_vars]} |
763 |
763 |
764 \item[@{text "t."}\hthm{case_cong_weak} @{text "[cong]"}\rm:] ~ \\ |
764 \item[\<open>t.\<close>\hthm{case_cong_weak} \<open>[cong]\<close>\rm:] ~ \\ |
765 @{thm list.case_cong_weak[no_vars]} |
765 @{thm list.case_cong_weak[no_vars]} |
766 |
766 |
767 \item[@{text "t."}\hthm{case_distrib}\rm:] ~ \\ |
767 \item[\<open>t.\<close>\hthm{case_distrib}\rm:] ~ \\ |
768 @{thm list.case_distrib[no_vars]} |
768 @{thm list.case_distrib[no_vars]} |
769 |
769 |
770 \item[@{text "t."}\hthm{split}\rm:] ~ \\ |
770 \item[\<open>t.\<close>\hthm{split}\rm:] ~ \\ |
771 @{thm list.split[no_vars]} |
771 @{thm list.split[no_vars]} |
772 |
772 |
773 \item[@{text "t."}\hthm{split_asm}\rm:] ~ \\ |
773 \item[\<open>t.\<close>\hthm{split_asm}\rm:] ~ \\ |
774 @{thm list.split_asm[no_vars]} |
774 @{thm list.split_asm[no_vars]} |
775 |
775 |
776 \item[@{text "t."}\hthm{splits} = @{text "split split_asm"}] |
776 \item[\<open>t.\<close>\hthm{splits} = \<open>split split_asm\<close>] |
777 |
777 |
778 \end{description} |
778 \end{description} |
779 \end{indentblock} |
779 \end{indentblock} |
780 |
780 |
781 \noindent |
781 \noindent |
782 The third subgroup revolves around discriminators and selectors: |
782 The third subgroup revolves around discriminators and selectors: |
783 |
783 |
784 \begin{indentblock} |
784 \begin{indentblock} |
785 \begin{description} |
785 \begin{description} |
786 |
786 |
787 \item[@{text "t."}\hthm{disc} @{text "[simp]"}\rm:] ~ \\ |
787 \item[\<open>t.\<close>\hthm{disc} \<open>[simp]\<close>\rm:] ~ \\ |
788 @{thm list.disc(1)[no_vars]} \\ |
788 @{thm list.disc(1)[no_vars]} \\ |
789 @{thm list.disc(2)[no_vars]} |
789 @{thm list.disc(2)[no_vars]} |
790 |
790 |
791 \item[@{text "t."}\hthm{discI}\rm:] ~ \\ |
791 \item[\<open>t.\<close>\hthm{discI}\rm:] ~ \\ |
792 @{thm list.discI(1)[no_vars]} \\ |
792 @{thm list.discI(1)[no_vars]} \\ |
793 @{thm list.discI(2)[no_vars]} |
793 @{thm list.discI(2)[no_vars]} |
794 |
794 |
795 \item[@{text "t."}\hthm{sel} @{text "[simp, code]"}\rm:] ~ \\ |
795 \item[\<open>t.\<close>\hthm{sel} \<open>[simp, code]\<close>\rm:] ~ \\ |
796 @{thm list.sel(1)[no_vars]} \\ |
796 @{thm list.sel(1)[no_vars]} \\ |
797 @{thm list.sel(2)[no_vars]} \\ |
797 @{thm list.sel(2)[no_vars]} \\ |
798 The @{text "[code]"} attribute is set by the @{text code} plugin |
798 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
799 (Section~\ref{ssec:code-generator}). |
799 (Section~\ref{ssec:code-generator}). |
800 |
800 |
801 \item[@{text "t."}\hthm{collapse} @{text "[simp]"}\rm:] ~ \\ |
801 \item[\<open>t.\<close>\hthm{collapse} \<open>[simp]\<close>\rm:] ~ \\ |
802 @{thm list.collapse(1)[no_vars]} \\ |
802 @{thm list.collapse(1)[no_vars]} \\ |
803 @{thm list.collapse(2)[no_vars]} \\ |
803 @{thm list.collapse(2)[no_vars]} \\ |
804 The @{text "[simp]"} attribute is exceptionally omitted for datatypes equipped |
804 The \<open>[simp]\<close> attribute is exceptionally omitted for datatypes equipped |
805 with a single nullary constructor, because a property of the form |
805 with a single nullary constructor, because a property of the form |
806 @{prop "x = C"} is not suitable as a simplification rule. |
806 @{prop "x = C"} is not suitable as a simplification rule. |
807 |
807 |
808 \item[@{text "t."}\hthm{distinct_disc} @{text "[dest]"}\rm:] ~ \\ |
808 \item[\<open>t.\<close>\hthm{distinct_disc} \<open>[dest]\<close>\rm:] ~ \\ |
809 These properties are missing for @{typ "'a list"} because there is only one |
809 These properties are missing for @{typ "'a list"} because there is only one |
810 proper discriminator. If the datatype had been introduced with a second |
810 proper discriminator. If the datatype had been introduced with a second |
811 discriminator called @{const nonnull}, they would have read as follows: \\[\jot] |
811 discriminator called @{const nonnull}, they would have read as follows: \\[\jot] |
812 @{prop "null list \<Longrightarrow> \<not> nonnull list"} \\ |
812 @{prop "null list \<Longrightarrow> \<not> nonnull list"} \\ |
813 @{prop "nonnull list \<Longrightarrow> \<not> null list"} |
813 @{prop "nonnull list \<Longrightarrow> \<not> null list"} |
814 |
814 |
815 \item[@{text "t."}\hthm{exhaust_disc} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
815 \item[\<open>t.\<close>\hthm{exhaust_disc} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm:] ~ \\ |
816 @{thm list.exhaust_disc[no_vars]} |
816 @{thm list.exhaust_disc[no_vars]} |
817 |
817 |
818 \item[@{text "t."}\hthm{exhaust_sel} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
818 \item[\<open>t.\<close>\hthm{exhaust_sel} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm:] ~ \\ |
819 @{thm list.exhaust_sel[no_vars]} |
819 @{thm list.exhaust_sel[no_vars]} |
820 |
820 |
821 \item[@{text "t."}\hthm{expand}\rm:] ~ \\ |
821 \item[\<open>t.\<close>\hthm{expand}\rm:] ~ \\ |
822 @{thm list.expand[no_vars]} |
822 @{thm list.expand[no_vars]} |
823 |
823 |
824 \item[@{text "t."}\hthm{split_sel}\rm:] ~ \\ |
824 \item[\<open>t.\<close>\hthm{split_sel}\rm:] ~ \\ |
825 @{thm list.split_sel[no_vars]} |
825 @{thm list.split_sel[no_vars]} |
826 |
826 |
827 \item[@{text "t."}\hthm{split_sel_asm}\rm:] ~ \\ |
827 \item[\<open>t.\<close>\hthm{split_sel_asm}\rm:] ~ \\ |
828 @{thm list.split_sel_asm[no_vars]} |
828 @{thm list.split_sel_asm[no_vars]} |
829 |
829 |
830 \item[@{text "t."}\hthm{split_sels} = @{text "split_sel split_sel_asm"}] |
830 \item[\<open>t.\<close>\hthm{split_sels} = \<open>split_sel split_sel_asm\<close>] |
831 |
831 |
832 \item[@{text "t."}\hthm{case_eq_if}\rm:] ~ \\ |
832 \item[\<open>t.\<close>\hthm{case_eq_if}\rm:] ~ \\ |
833 @{thm list.case_eq_if[no_vars]} |
833 @{thm list.case_eq_if[no_vars]} |
834 |
834 |
835 \item[@{text "t."}\hthm{disc_eq_case}\rm:] ~ \\ |
835 \item[\<open>t.\<close>\hthm{disc_eq_case}\rm:] ~ \\ |
836 @{thm list.disc_eq_case(1)[no_vars]} \\ |
836 @{thm list.disc_eq_case(1)[no_vars]} \\ |
837 @{thm list.disc_eq_case(2)[no_vars]} |
837 @{thm list.disc_eq_case(2)[no_vars]} |
838 |
838 |
839 \end{description} |
839 \end{description} |
840 \end{indentblock} |
840 \end{indentblock} |
841 |
841 |
842 \noindent |
842 \noindent |
843 In addition, equational versions of @{text t.disc} are registered with the |
843 In addition, equational versions of \<open>t.disc\<close> are registered with the |
844 @{text "[code]"} attribute. The @{text "[code]"} attribute is set by the |
844 \<open>[code]\<close> attribute. The \<open>[code]\<close> attribute is set by the |
845 @{text code} plugin (Section~\ref{ssec:code-generator}). |
845 \<open>code\<close> plugin (Section~\ref{ssec:code-generator}). |
846 \<close> |
846 \<close> |
847 |
847 |
848 |
848 |
849 subsubsection \<open>Functorial Theorems |
849 subsubsection \<open>Functorial Theorems |
850 \label{sssec:functorial-theorems}\<close> |
850 \label{sssec:functorial-theorems}\<close> |
857 the predicator, or the relator: |
857 the predicator, or the relator: |
858 |
858 |
859 \begin{indentblock} |
859 \begin{indentblock} |
860 \begin{description} |
860 \begin{description} |
861 |
861 |
862 \item[@{text "t."}\hthm{case_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
862 \item[\<open>t.\<close>\hthm{case_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
863 @{thm list.case_transfer[no_vars]} \\ |
863 @{thm list.case_transfer[no_vars]} \\ |
864 This property is generated by the @{text transfer} plugin |
864 This property is generated by the \<open>transfer\<close> plugin |
865 (Section~\ref{ssec:transfer}). |
865 (Section~\ref{ssec:transfer}). |
866 %The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
866 %The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
867 %(Section~\ref{ssec:transfer}). |
867 %(Section~\ref{ssec:transfer}). |
868 |
868 |
869 \item[@{text "t."}\hthm{sel_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
869 \item[\<open>t.\<close>\hthm{sel_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
870 This property is missing for @{typ "'a list"} because there is no common |
870 This property is missing for @{typ "'a list"} because there is no common |
871 selector to all constructors. \\ |
871 selector to all constructors. \\ |
872 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
872 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
873 (Section~\ref{ssec:transfer}). |
873 (Section~\ref{ssec:transfer}). |
874 |
874 |
875 \item[@{text "t."}\hthm{ctr_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
875 \item[\<open>t.\<close>\hthm{ctr_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
876 @{thm list.ctr_transfer(1)[no_vars]} \\ |
876 @{thm list.ctr_transfer(1)[no_vars]} \\ |
877 @{thm list.ctr_transfer(2)[no_vars]} \\ |
877 @{thm list.ctr_transfer(2)[no_vars]} \\ |
878 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
878 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
879 (Section~\ref{ssec:transfer}) . |
879 (Section~\ref{ssec:transfer}) . |
880 |
880 |
881 \item[@{text "t."}\hthm{disc_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
881 \item[\<open>t.\<close>\hthm{disc_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
882 @{thm list.disc_transfer(1)[no_vars]} \\ |
882 @{thm list.disc_transfer(1)[no_vars]} \\ |
883 @{thm list.disc_transfer(2)[no_vars]} \\ |
883 @{thm list.disc_transfer(2)[no_vars]} \\ |
884 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
884 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
885 (Section~\ref{ssec:transfer}). |
885 (Section~\ref{ssec:transfer}). |
886 |
886 |
887 \item[@{text "t."}\hthm{set} @{text "[simp, code]"}\rm:] ~ \\ |
887 \item[\<open>t.\<close>\hthm{set} \<open>[simp, code]\<close>\rm:] ~ \\ |
888 @{thm list.set(1)[no_vars]} \\ |
888 @{thm list.set(1)[no_vars]} \\ |
889 @{thm list.set(2)[no_vars]} \\ |
889 @{thm list.set(2)[no_vars]} \\ |
890 The @{text "[code]"} attribute is set by the @{text code} plugin |
890 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
891 (Section~\ref{ssec:code-generator}). |
891 (Section~\ref{ssec:code-generator}). |
892 |
892 |
893 \item[@{text "t."}\hthm{set_cases} @{text "[consumes 1, cases set: set\<^sub>i_t]"}\rm:] ~ \\ |
893 \item[\<open>t.\<close>\hthm{set_cases} \<open>[consumes 1, cases set: set\<^sub>i_t]\<close>\rm:] ~ \\ |
894 @{thm list.set_cases[no_vars]} |
894 @{thm list.set_cases[no_vars]} |
895 |
895 |
896 \item[@{text "t."}\hthm{set_intros}\rm:] ~ \\ |
896 \item[\<open>t.\<close>\hthm{set_intros}\rm:] ~ \\ |
897 @{thm list.set_intros(1)[no_vars]} \\ |
897 @{thm list.set_intros(1)[no_vars]} \\ |
898 @{thm list.set_intros(2)[no_vars]} |
898 @{thm list.set_intros(2)[no_vars]} |
899 |
899 |
900 \item[@{text "t."}\hthm{set_sel}\rm:] ~ \\ |
900 \item[\<open>t.\<close>\hthm{set_sel}\rm:] ~ \\ |
901 @{thm list.set_sel[no_vars]} |
901 @{thm list.set_sel[no_vars]} |
902 |
902 |
903 \item[@{text "t."}\hthm{map} @{text "[simp, code]"}\rm:] ~ \\ |
903 \item[\<open>t.\<close>\hthm{map} \<open>[simp, code]\<close>\rm:] ~ \\ |
904 @{thm list.map(1)[no_vars]} \\ |
904 @{thm list.map(1)[no_vars]} \\ |
905 @{thm list.map(2)[no_vars]} \\ |
905 @{thm list.map(2)[no_vars]} \\ |
906 The @{text "[code]"} attribute is set by the @{text code} plugin |
906 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
907 (Section~\ref{ssec:code-generator}). |
907 (Section~\ref{ssec:code-generator}). |
908 |
908 |
909 \item[@{text "t."}\hthm{map_disc_iff} @{text "[simp]"}\rm:] ~ \\ |
909 \item[\<open>t.\<close>\hthm{map_disc_iff} \<open>[simp]\<close>\rm:] ~ \\ |
910 @{thm list.map_disc_iff[no_vars]} |
910 @{thm list.map_disc_iff[no_vars]} |
911 |
911 |
912 \item[@{text "t."}\hthm{map_sel}\rm:] ~ \\ |
912 \item[\<open>t.\<close>\hthm{map_sel}\rm:] ~ \\ |
913 @{thm list.map_sel[no_vars]} |
913 @{thm list.map_sel[no_vars]} |
914 |
914 |
915 \item[@{text "t."}\hthm{pred_inject} @{text "[simp]"}\rm:] ~ \\ |
915 \item[\<open>t.\<close>\hthm{pred_inject} \<open>[simp]\<close>\rm:] ~ \\ |
916 @{thm list.pred_inject(1)[no_vars]} \\ |
916 @{thm list.pred_inject(1)[no_vars]} \\ |
917 @{thm list.pred_inject(2)[no_vars]} |
917 @{thm list.pred_inject(2)[no_vars]} |
918 |
918 |
919 \item[@{text "t."}\hthm{rel_inject} @{text "[simp]"}\rm:] ~ \\ |
919 \item[\<open>t.\<close>\hthm{rel_inject} \<open>[simp]\<close>\rm:] ~ \\ |
920 @{thm list.rel_inject(1)[no_vars]} \\ |
920 @{thm list.rel_inject(1)[no_vars]} \\ |
921 @{thm list.rel_inject(2)[no_vars]} |
921 @{thm list.rel_inject(2)[no_vars]} |
922 |
922 |
923 \item[@{text "t."}\hthm{rel_distinct} @{text "[simp]"}\rm:] ~ \\ |
923 \item[\<open>t.\<close>\hthm{rel_distinct} \<open>[simp]\<close>\rm:] ~ \\ |
924 @{thm list.rel_distinct(1)[no_vars]} \\ |
924 @{thm list.rel_distinct(1)[no_vars]} \\ |
925 @{thm list.rel_distinct(2)[no_vars]} |
925 @{thm list.rel_distinct(2)[no_vars]} |
926 |
926 |
927 \item[@{text "t."}\hthm{rel_intros}\rm:] ~ \\ |
927 \item[\<open>t.\<close>\hthm{rel_intros}\rm:] ~ \\ |
928 @{thm list.rel_intros(1)[no_vars]} \\ |
928 @{thm list.rel_intros(1)[no_vars]} \\ |
929 @{thm list.rel_intros(2)[no_vars]} |
929 @{thm list.rel_intros(2)[no_vars]} |
930 |
930 |
931 \item[@{text "t."}\hthm{rel_cases} @{text "[consumes 1, case_names t\<^sub>1 \<dots> t\<^sub>m, cases pred]"}\rm:] ~ \\ |
931 \item[\<open>t.\<close>\hthm{rel_cases} \<open>[consumes 1, case_names t\<^sub>1 \<dots> t\<^sub>m, cases pred]\<close>\rm:] ~ \\ |
932 @{thm list.rel_cases[no_vars]} |
932 @{thm list.rel_cases[no_vars]} |
933 |
933 |
934 \item[@{text "t."}\hthm{rel_sel}\rm:] ~ \\ |
934 \item[\<open>t.\<close>\hthm{rel_sel}\rm:] ~ \\ |
935 @{thm list.rel_sel[no_vars]} |
935 @{thm list.rel_sel[no_vars]} |
936 |
936 |
937 \end{description} |
937 \end{description} |
938 \end{indentblock} |
938 \end{indentblock} |
939 |
939 |
940 \noindent |
940 \noindent |
941 In addition, equational versions of @{text t.rel_inject} and @{text |
941 In addition, equational versions of \<open>t.rel_inject\<close> and \<open>rel_distinct\<close> are registered with the \<open>[code]\<close> attribute. The |
942 rel_distinct} are registered with the @{text "[code]"} attribute. The |
942 \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
943 @{text "[code]"} attribute is set by the @{text code} plugin |
|
944 (Section~\ref{ssec:code-generator}). |
943 (Section~\ref{ssec:code-generator}). |
945 |
944 |
946 The second subgroup consists of more abstract properties of the set functions, |
945 The second subgroup consists of more abstract properties of the set functions, |
947 the map function, the predicator, and the relator: |
946 the map function, the predicator, and the relator: |
948 |
947 |
949 \begin{indentblock} |
948 \begin{indentblock} |
950 \begin{description} |
949 \begin{description} |
951 |
950 |
952 \item[@{text "t."}\hthm{inj_map}\rm:] ~ \\ |
951 \item[\<open>t.\<close>\hthm{inj_map}\rm:] ~ \\ |
953 @{thm list.inj_map[no_vars]} |
952 @{thm list.inj_map[no_vars]} |
954 |
953 |
955 \item[@{text "t."}\hthm{inj_map_strong}\rm:] ~ \\ |
954 \item[\<open>t.\<close>\hthm{inj_map_strong}\rm:] ~ \\ |
956 @{thm list.inj_map_strong[no_vars]} |
955 @{thm list.inj_map_strong[no_vars]} |
957 |
956 |
958 \item[@{text "t."}\hthm{map_comp}\rm:] ~ \\ |
957 \item[\<open>t.\<close>\hthm{map_comp}\rm:] ~ \\ |
959 @{thm list.map_comp[no_vars]} |
958 @{thm list.map_comp[no_vars]} |
960 |
959 |
961 \item[@{text "t."}\hthm{map_cong0}\rm:] ~ \\ |
960 \item[\<open>t.\<close>\hthm{map_cong0}\rm:] ~ \\ |
962 @{thm list.map_cong0[no_vars]} |
961 @{thm list.map_cong0[no_vars]} |
963 |
962 |
964 \item[@{text "t."}\hthm{map_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
963 \item[\<open>t.\<close>\hthm{map_cong} \<open>[fundef_cong]\<close>\rm:] ~ \\ |
965 @{thm list.map_cong[no_vars]} |
964 @{thm list.map_cong[no_vars]} |
966 |
965 |
967 \item[@{text "t."}\hthm{map_cong_pred}\rm:] ~ \\ |
966 \item[\<open>t.\<close>\hthm{map_cong_pred}\rm:] ~ \\ |
968 @{thm list.map_cong_pred[no_vars]} |
967 @{thm list.map_cong_pred[no_vars]} |
969 |
968 |
970 \item[@{text "t."}\hthm{map_cong_simp}\rm:] ~ \\ |
969 \item[\<open>t.\<close>\hthm{map_cong_simp}\rm:] ~ \\ |
971 @{thm list.map_cong_simp[no_vars]} |
970 @{thm list.map_cong_simp[no_vars]} |
972 |
971 |
973 \item[@{text "t."}\hthm{map_id0}\rm:] ~ \\ |
972 \item[\<open>t.\<close>\hthm{map_id0}\rm:] ~ \\ |
974 @{thm list.map_id0[no_vars]} |
973 @{thm list.map_id0[no_vars]} |
975 |
974 |
976 \item[@{text "t."}\hthm{map_id}\rm:] ~ \\ |
975 \item[\<open>t.\<close>\hthm{map_id}\rm:] ~ \\ |
977 @{thm list.map_id[no_vars]} |
976 @{thm list.map_id[no_vars]} |
978 |
977 |
979 \item[@{text "t."}\hthm{map_ident}\rm:] ~ \\ |
978 \item[\<open>t.\<close>\hthm{map_ident}\rm:] ~ \\ |
980 @{thm list.map_ident[no_vars]} |
979 @{thm list.map_ident[no_vars]} |
981 |
980 |
982 \item[@{text "t."}\hthm{map_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
981 \item[\<open>t.\<close>\hthm{map_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
983 @{thm list.map_transfer[no_vars]} \\ |
982 @{thm list.map_transfer[no_vars]} \\ |
984 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
983 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
985 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
984 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
986 |
985 |
987 \item[@{text "t."}\hthm{pred_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
986 \item[\<open>t.\<close>\hthm{pred_cong} \<open>[fundef_cong]\<close>\rm:] ~ \\ |
988 @{thm list.pred_cong[no_vars]} |
987 @{thm list.pred_cong[no_vars]} |
989 |
988 |
990 \item[@{text "t."}\hthm{pred_cong_simp}\rm:] ~ \\ |
989 \item[\<open>t.\<close>\hthm{pred_cong_simp}\rm:] ~ \\ |
991 @{thm list.pred_cong_simp[no_vars]} |
990 @{thm list.pred_cong_simp[no_vars]} |
992 |
991 |
993 \item[@{text "t."}\hthm{pred_map}\rm:] ~ \\ |
992 \item[\<open>t.\<close>\hthm{pred_map}\rm:] ~ \\ |
994 @{thm list.pred_map[no_vars]} |
993 @{thm list.pred_map[no_vars]} |
995 |
994 |
996 \item[@{text "t."}\hthm{pred_mono_strong}\rm:] ~ \\ |
995 \item[\<open>t.\<close>\hthm{pred_mono_strong}\rm:] ~ \\ |
997 @{thm list.pred_mono_strong[no_vars]} |
996 @{thm list.pred_mono_strong[no_vars]} |
998 |
997 |
999 \item[@{text "t."}\hthm{pred_rel}\rm:] ~ \\ |
998 \item[\<open>t.\<close>\hthm{pred_rel}\rm:] ~ \\ |
1000 @{thm list.pred_rel[no_vars]} |
999 @{thm list.pred_rel[no_vars]} |
1001 |
1000 |
1002 \item[@{text "t."}\hthm{pred_set}\rm:] ~ \\ |
1001 \item[\<open>t.\<close>\hthm{pred_set}\rm:] ~ \\ |
1003 @{thm list.pred_set[no_vars]} |
1002 @{thm list.pred_set[no_vars]} |
1004 |
1003 |
1005 \item[@{text "t."}\hthm{pred_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1004 \item[\<open>t.\<close>\hthm{pred_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
1006 @{thm list.pred_transfer[no_vars]} \\ |
1005 @{thm list.pred_transfer[no_vars]} \\ |
1007 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
1006 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
1008 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1007 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1009 |
1008 |
1010 \item[@{text "t."}\hthm{pred_True}\rm:] ~ \\ |
1009 \item[\<open>t.\<close>\hthm{pred_True}\rm:] ~ \\ |
1011 @{thm list.pred_True[no_vars]} |
1010 @{thm list.pred_True[no_vars]} |
1012 |
1011 |
1013 \item[@{text "t."}\hthm{set_map}\rm:] ~ \\ |
1012 \item[\<open>t.\<close>\hthm{set_map}\rm:] ~ \\ |
1014 @{thm list.set_map[no_vars]} |
1013 @{thm list.set_map[no_vars]} |
1015 |
1014 |
1016 \item[@{text "t."}\hthm{set_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1015 \item[\<open>t.\<close>\hthm{set_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
1017 @{thm list.set_transfer[no_vars]} \\ |
1016 @{thm list.set_transfer[no_vars]} \\ |
1018 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
1017 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
1019 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1018 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1020 |
1019 |
1021 \item[@{text "t."}\hthm{rel_compp} @{text "[relator_distr]"}\rm:] ~ \\ |
1020 \item[\<open>t.\<close>\hthm{rel_compp} \<open>[relator_distr]\<close>\rm:] ~ \\ |
1022 @{thm list.rel_compp[no_vars]} \\ |
1021 @{thm list.rel_compp[no_vars]} \\ |
1023 The @{text "[relator_distr]"} attribute is set by the @{text lifting} plugin |
1022 The \<open>[relator_distr]\<close> attribute is set by the \<open>lifting\<close> plugin |
1024 (Section~\ref{ssec:lifting}). |
1023 (Section~\ref{ssec:lifting}). |
1025 |
1024 |
1026 \item[@{text "t."}\hthm{rel_conversep}\rm:] ~ \\ |
1025 \item[\<open>t.\<close>\hthm{rel_conversep}\rm:] ~ \\ |
1027 @{thm list.rel_conversep[no_vars]} |
1026 @{thm list.rel_conversep[no_vars]} |
1028 |
1027 |
1029 \item[@{text "t."}\hthm{rel_eq}\rm:] ~ \\ |
1028 \item[\<open>t.\<close>\hthm{rel_eq}\rm:] ~ \\ |
1030 @{thm list.rel_eq[no_vars]} |
1029 @{thm list.rel_eq[no_vars]} |
1031 |
1030 |
1032 \item[@{text "t."}\hthm{rel_eq_onp}\rm:] ~ \\ |
1031 \item[\<open>t.\<close>\hthm{rel_eq_onp}\rm:] ~ \\ |
1033 @{thm list.rel_eq_onp[no_vars]} |
1032 @{thm list.rel_eq_onp[no_vars]} |
1034 |
1033 |
1035 \item[@{text "t."}\hthm{rel_flip}\rm:] ~ \\ |
1034 \item[\<open>t.\<close>\hthm{rel_flip}\rm:] ~ \\ |
1036 @{thm list.rel_flip[no_vars]} |
1035 @{thm list.rel_flip[no_vars]} |
1037 |
1036 |
1038 \item[@{text "t."}\hthm{rel_map}\rm:] ~ \\ |
1037 \item[\<open>t.\<close>\hthm{rel_map}\rm:] ~ \\ |
1039 @{thm list.rel_map(1)[no_vars]} \\ |
1038 @{thm list.rel_map(1)[no_vars]} \\ |
1040 @{thm list.rel_map(2)[no_vars]} |
1039 @{thm list.rel_map(2)[no_vars]} |
1041 |
1040 |
1042 \item[@{text "t."}\hthm{rel_mono} @{text "[mono, relator_mono]"}\rm:] ~ \\ |
1041 \item[\<open>t.\<close>\hthm{rel_mono} \<open>[mono, relator_mono]\<close>\rm:] ~ \\ |
1043 @{thm list.rel_mono[no_vars]} \\ |
1042 @{thm list.rel_mono[no_vars]} \\ |
1044 The @{text "[relator_mono]"} attribute is set by the @{text lifting} plugin |
1043 The \<open>[relator_mono]\<close> attribute is set by the \<open>lifting\<close> plugin |
1045 (Section~\ref{ssec:lifting}). |
1044 (Section~\ref{ssec:lifting}). |
1046 |
1045 |
1047 \item[@{text "t."}\hthm{rel_mono_strong}\rm:] ~ \\ |
1046 \item[\<open>t.\<close>\hthm{rel_mono_strong}\rm:] ~ \\ |
1048 @{thm list.rel_mono_strong[no_vars]} |
1047 @{thm list.rel_mono_strong[no_vars]} |
1049 |
1048 |
1050 \item[@{text "t."}\hthm{rel_cong} @{text "[fundef_cong]"}\rm:] ~ \\ |
1049 \item[\<open>t.\<close>\hthm{rel_cong} \<open>[fundef_cong]\<close>\rm:] ~ \\ |
1051 @{thm list.rel_cong[no_vars]} |
1050 @{thm list.rel_cong[no_vars]} |
1052 |
1051 |
1053 \item[@{text "t."}\hthm{rel_cong_simp}\rm:] ~ \\ |
1052 \item[\<open>t.\<close>\hthm{rel_cong_simp}\rm:] ~ \\ |
1054 @{thm list.rel_cong_simp[no_vars]} |
1053 @{thm list.rel_cong_simp[no_vars]} |
1055 |
1054 |
1056 \item[@{text "t."}\hthm{rel_refl}\rm:] ~ \\ |
1055 \item[\<open>t.\<close>\hthm{rel_refl}\rm:] ~ \\ |
1057 @{thm list.rel_refl[no_vars]} |
1056 @{thm list.rel_refl[no_vars]} |
1058 |
1057 |
1059 \item[@{text "t."}\hthm{rel_refl_strong}\rm:] ~ \\ |
1058 \item[\<open>t.\<close>\hthm{rel_refl_strong}\rm:] ~ \\ |
1060 @{thm list.rel_refl_strong[no_vars]} |
1059 @{thm list.rel_refl_strong[no_vars]} |
1061 |
1060 |
1062 \item[@{text "t."}\hthm{rel_reflp}\rm:] ~ \\ |
1061 \item[\<open>t.\<close>\hthm{rel_reflp}\rm:] ~ \\ |
1063 @{thm list.rel_reflp[no_vars]} |
1062 @{thm list.rel_reflp[no_vars]} |
1064 |
1063 |
1065 \item[@{text "t."}\hthm{rel_symp}\rm:] ~ \\ |
1064 \item[\<open>t.\<close>\hthm{rel_symp}\rm:] ~ \\ |
1066 @{thm list.rel_symp[no_vars]} |
1065 @{thm list.rel_symp[no_vars]} |
1067 |
1066 |
1068 \item[@{text "t."}\hthm{rel_transp}\rm:] ~ \\ |
1067 \item[\<open>t.\<close>\hthm{rel_transp}\rm:] ~ \\ |
1069 @{thm list.rel_transp[no_vars]} |
1068 @{thm list.rel_transp[no_vars]} |
1070 |
1069 |
1071 \item[@{text "t."}\hthm{rel_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1070 \item[\<open>t.\<close>\hthm{rel_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
1072 @{thm list.rel_transfer[no_vars]} \\ |
1071 @{thm list.rel_transfer[no_vars]} \\ |
1073 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
1072 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
1074 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1073 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1075 |
1074 |
1076 \end{description} |
1075 \end{description} |
1077 \end{indentblock} |
1076 \end{indentblock} |
1078 \<close> |
1077 \<close> |
1085 The inductive theorems are as follows: |
1084 The inductive theorems are as follows: |
1086 |
1085 |
1087 \begin{indentblock} |
1086 \begin{indentblock} |
1088 \begin{description} |
1087 \begin{description} |
1089 |
1088 |
1090 \item[@{text "t."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n, induct t]"}\rm:] ~ \\ |
1089 \item[\<open>t.\<close>\hthm{induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n, induct t]\<close>\rm:] ~ \\ |
1091 @{thm list.induct[no_vars]} |
1090 @{thm list.induct[no_vars]} |
1092 |
1091 |
1093 \item[@{text "t."}\hthm{rel_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n, induct pred]"}\rm:] ~ \\ |
1092 \item[\<open>t.\<close>\hthm{rel_induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n, induct pred]\<close>\rm:] ~ \\ |
1094 @{thm list.rel_induct[no_vars]} |
1093 @{thm list.rel_induct[no_vars]} |
1095 |
1094 |
1096 \item[\begin{tabular}{@ {}l@ {}} |
1095 \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: \\ |
1096 \<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm: \\ |
1098 @{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm: \\ |
1097 \<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{rel_induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm: \\ |
1099 \end{tabular}] ~ \\ |
1098 \end{tabular}] ~ \\ |
1100 Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
1099 Given $m > 1$ mutually recursive datatypes, this induction rule can be used to |
1101 prove $m$ properties simultaneously. |
1100 prove $m$ properties simultaneously. |
1102 |
1101 |
1103 \item[@{text "t."}\hthm{rec} @{text "[simp, code]"}\rm:] ~ \\ |
1102 \item[\<open>t.\<close>\hthm{rec} \<open>[simp, code]\<close>\rm:] ~ \\ |
1104 @{thm list.rec(1)[no_vars]} \\ |
1103 @{thm list.rec(1)[no_vars]} \\ |
1105 @{thm list.rec(2)[no_vars]} \\ |
1104 @{thm list.rec(2)[no_vars]} \\ |
1106 The @{text "[code]"} attribute is set by the @{text code} plugin |
1105 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
1107 (Section~\ref{ssec:code-generator}). |
1106 (Section~\ref{ssec:code-generator}). |
1108 |
1107 |
1109 \item[@{text "t."}\hthm{rec_o_map}\rm:] ~ \\ |
1108 \item[\<open>t.\<close>\hthm{rec_o_map}\rm:] ~ \\ |
1110 @{thm list.rec_o_map[no_vars]} |
1109 @{thm list.rec_o_map[no_vars]} |
1111 |
1110 |
1112 \item[@{text "t."}\hthm{rec_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1111 \item[\<open>t.\<close>\hthm{rec_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
1113 @{thm list.rec_transfer[no_vars]} \\ |
1112 @{thm list.rec_transfer[no_vars]} \\ |
1114 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
1113 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
1115 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1114 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1116 |
1115 |
1117 \end{description} |
1116 \end{description} |
1118 \end{indentblock} |
1117 \end{indentblock} |
1119 |
1118 |
1121 For convenience, @{command datatype} also provides the following collection: |
1120 For convenience, @{command datatype} also provides the following collection: |
1122 |
1121 |
1123 \begin{indentblock} |
1122 \begin{indentblock} |
1124 \begin{description} |
1123 \begin{description} |
1125 |
1124 |
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} \\ |
1125 \item[\<open>t.\<close>\hthm{simps}] = \<open>t.inject\<close> \<open>t.distinct\<close> \<open>t.case\<close> \<open>t.rec\<close> \<open>t.map\<close> \<open>t.rel_inject\<close> \\ |
1127 @{text t.rel_distinct} @{text t.set} |
1126 \<open>t.rel_distinct\<close> \<open>t.set\<close> |
1128 |
1127 |
1129 \end{description} |
1128 \end{description} |
1130 \end{indentblock} |
1129 \end{indentblock} |
1131 \<close> |
1130 \<close> |
1132 |
1131 |
1159 \begin{itemize} |
1158 \begin{itemize} |
1160 \setlength{\itemsep}{0pt} |
1159 \setlength{\itemsep}{0pt} |
1161 |
1160 |
1162 \item \emph{The Standard ML interfaces are different.} Tools and extensions |
1161 \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 |
1162 written to call the old ML interfaces will need to be adapted to the new |
1164 interfaces. The @{text BNF_LFP_Compat} structure provides convenience functions |
1163 interfaces. The \<open>BNF_LFP_Compat\<close> structure provides convenience functions |
1165 that simulate the old interfaces in terms of the new ones. |
1164 that simulate the old interfaces in terms of the new ones. |
1166 |
1165 |
1167 \item \emph{The recursor @{text rec_t} has a different signature for nested |
1166 \item \emph{The recursor \<open>rec_t\<close> has a different signature for nested |
1168 recursive datatypes.} In the old package, nested recursion through non-functions |
1167 recursive datatypes.} In the old package, nested recursion through non-functions |
1169 was internally reduced to mutual recursion. This reduction was visible in the |
1168 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 |
1169 type of the recursor, used by \keyw{primrec}. Recursion through functions was |
1171 handled specially. In the new package, nested recursion (for functions and |
1170 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 |
1171 non-functions) is handled in a more modular fashion. The old-style recursor can |
1178 \item \emph{Accordingly, the induction rule is different for nested recursive |
1177 \item \emph{Accordingly, the induction rule is different for nested recursive |
1179 datatypes.} Again, the old-style induction rule can be generated on demand |
1178 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 |
1179 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 |
1180 explained in Section~\ref{sssec:primrec-nested-as-mutual-recursion}, or using |
1182 @{command datatype_compat}. For recursion through functions, the old-style |
1181 @{command datatype_compat}. For recursion through functions, the old-style |
1183 induction rule can be obtained by applying the @{text "[unfolded |
1182 induction rule can be obtained by applying the \<open>[unfolded |
1184 all_mem_range]"} attribute on @{text t.induct}. |
1183 all_mem_range]\<close> attribute on \<open>t.induct\<close>. |
1185 |
1184 |
1186 \item \emph{The @{const size} function has a slightly different definition.} |
1185 \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 |
1186 The new function returns \<open>1\<close> instead of \<open>0\<close> for some nonrecursive |
1188 constructors. This departure from the old behavior made it possible to implement |
1187 constructors. This departure from the old behavior made it possible to implement |
1189 @{const size} in terms of the generic function @{text "t.size_t"}. Moreover, |
1188 @{const size} in terms of the generic function \<open>t.size_t\<close>. Moreover, |
1190 the new function considers nested occurrences of a value, in the nested |
1189 the new function considers nested occurrences of a value, in the nested |
1191 recursive case. The old behavior can be obtained by disabling the @{text size} |
1190 recursive case. The old behavior can be obtained by disabling the \<open>size\<close> |
1192 plugin (Section~\ref{sec:selecting-plugins}) and instantiating the |
1191 plugin (Section~\ref{sec:selecting-plugins}) and instantiating the |
1193 @{text size} type class manually. |
1192 \<open>size\<close> type class manually. |
1194 |
1193 |
1195 \item \emph{The internal constructions are completely different.} Proof texts |
1194 \item \emph{The internal constructions are completely different.} Proof texts |
1196 that unfold the definition of constants introduced by the old command will |
1195 that unfold the definition of constants introduced by the old command will |
1197 be difficult to port. |
1196 be difficult to port. |
1198 |
1197 |
1199 \item \emph{Some constants and theorems have different names.} |
1198 \item \emph{Some constants and theorems have different names.} |
1200 For non-mutually recursive datatypes, |
1199 For non-mutually recursive datatypes, |
1201 the alias @{text t.inducts} for @{text t.induct} is no longer generated. |
1200 the alias \<open>t.inducts\<close> for \<open>t.induct\<close> is no longer generated. |
1202 For $m > 1$ mutually recursive datatypes, |
1201 For $m > 1$ mutually recursive datatypes, |
1203 @{text "rec_t\<^sub>1_\<dots>_t\<^sub>m_i"} has been renamed |
1202 \<open>rec_t\<^sub>1_\<dots>_t\<^sub>m_i\<close> has been renamed |
1204 @{text "rec_t\<^sub>i"} for each @{text "i \<in> {1, \<dots>, m}"}, |
1203 \<open>rec_t\<^sub>i\<close> for each \<open>i \<in> {1, \<dots>, m}\<close>, |
1205 @{text "t\<^sub>1_\<dots>_t\<^sub>m.inducts(i)"} has been renamed |
1204 \<open>t\<^sub>1_\<dots>_t\<^sub>m.inducts(i)\<close> has been renamed |
1206 @{text "t\<^sub>i.induct"} for each @{text "i \<in> {1, \<dots>, m}"}, and the |
1205 \<open>t\<^sub>i.induct\<close> for each \<open>i \<in> {1, \<dots>, m}\<close>, and the |
1207 collection @{text "t\<^sub>1_\<dots>_t\<^sub>m.size"} (generated by the |
1206 collection \<open>t\<^sub>1_\<dots>_t\<^sub>m.size\<close> (generated by the |
1208 @{text size} plugin, Section~\ref{ssec:size}) has been divided into |
1207 \<open>size\<close> plugin, Section~\ref{ssec:size}) has been divided into |
1209 @{text "t\<^sub>1.size"}, \ldots, @{text "t\<^sub>m.size"}. |
1208 \<open>t\<^sub>1.size\<close>, \ldots, \<open>t\<^sub>m.size\<close>. |
1210 |
1209 |
1211 \item \emph{The @{text t.simps} collection has been extended.} |
1210 \item \emph{The \<open>t.simps\<close> collection has been extended.} |
1212 Previously available theorems are available at the same index as before. |
1211 Previously available theorems are available at the same index as before. |
1213 |
1212 |
1214 \item \emph{Variables in generated properties have different names.} This is |
1213 \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 |
1214 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 |
1215 \<open>[where \<dots>]\<close> attribute. The solution is to use the more robust |
1217 @{text "[of \<dots>]"} syntax. |
1216 \<open>[of \<dots>]\<close> syntax. |
1218 \end{itemize} |
1217 \end{itemize} |
1219 \<close> |
1218 \<close> |
1220 |
1219 |
1221 |
1220 |
1222 section \<open>Defining Primitively Recursive Functions |
1221 section \<open>Defining Primitively Recursive Functions |
1394 [] \<Rightarrow> a |
1393 [] \<Rightarrow> a |
1395 | j # js' \<Rightarrow> at (map (\<lambda>t. at\<^sub>f\<^sub>f t js') ts) j)" |
1394 | j # js' \<Rightarrow> at (map (\<lambda>t. at\<^sub>f\<^sub>f t js') ts) j)" |
1396 |
1395 |
1397 text \<open> |
1396 text \<open> |
1398 \noindent |
1397 \noindent |
1399 The next example features recursion through the @{text option} type. Although |
1398 The next example features recursion through the \<open>option\<close> type. Although |
1400 @{text option} is not a new-style datatype, it is registered as a BNF with the |
1399 \<open>option\<close> is not a new-style datatype, it is registered as a BNF with the |
1401 map function @{const map_option}: |
1400 map function @{const map_option}: |
1402 \<close> |
1401 \<close> |
1403 |
1402 |
1404 primrec (*<*)(in early) (*>*)sum_btree :: "('a::{zero,plus}) btree \<Rightarrow> 'a" where |
1403 primrec (*<*)(in early) (*>*)sum_btree :: "('a::{zero,plus}) btree \<Rightarrow> 'a" where |
1405 "sum_btree (BNode a lt rt) = |
1404 "sum_btree (BNode a lt rt) = |
1408 |
1407 |
1409 text \<open> |
1408 text \<open> |
1410 \noindent |
1409 \noindent |
1411 The same principle applies for arbitrary type constructors through which |
1410 The same principle applies for arbitrary type constructors through which |
1412 recursion is possible. Notably, the map function for the function type |
1411 recursion is possible. Notably, the map function for the function type |
1413 (@{text \<Rightarrow>}) is simply composition (@{text "(\<circ>)"}): |
1412 (\<open>\<Rightarrow>\<close>) is simply composition (\<open>(\<circ>)\<close>): |
1414 \<close> |
1413 \<close> |
1415 |
1414 |
1416 primrec (*<*)(in early) (*>*)relabel_ft :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
1415 primrec (*<*)(in early) (*>*)relabel_ft :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a ftree \<Rightarrow> 'a ftree" where |
1417 "relabel_ft f (FTLeaf x) = FTLeaf (f x)" |
1416 "relabel_ft f (FTLeaf x) = FTLeaf (f x)" |
1418 | "relabel_ft f (FTNode g) = FTNode (relabel_ft f \<circ> g)" |
1417 | "relabel_ft f (FTNode g) = FTNode (relabel_ft f \<circ> g)" |
1557 subsubsection \<open>\keyw{primrec} |
1556 subsubsection \<open>\keyw{primrec} |
1558 \label{sssec:primrec}\<close> |
1557 \label{sssec:primrec}\<close> |
1559 |
1558 |
1560 text \<open> |
1559 text \<open> |
1561 \begin{matharray}{rcl} |
1560 \begin{matharray}{rcl} |
1562 @{command_def "primrec"} & : & @{text "local_theory \<rightarrow> local_theory"} |
1561 @{command_def "primrec"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
1563 \end{matharray} |
1562 \end{matharray} |
1564 |
1563 |
1565 @{rail \<open> |
1564 @{rail \<open> |
1566 @@{command primrec} target? @{syntax pr_options}? fixes \<newline> |
1565 @@{command primrec} target? @{syntax pr_options}? fixes \<newline> |
1567 @'where' (@{syntax pr_equation} + '|') |
1566 @'where' (@{syntax pr_equation} + '|') |
1587 |
1586 |
1588 \begin{itemize} |
1587 \begin{itemize} |
1589 \setlength{\itemsep}{0pt} |
1588 \setlength{\itemsep}{0pt} |
1590 |
1589 |
1591 \item |
1590 \item |
1592 The @{text plugins} option indicates which plugins should be enabled |
1591 The \<open>plugins\<close> option indicates which plugins should be enabled |
1593 (@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
1592 (\<open>only\<close>) or disabled (\<open>del\<close>). By default, all plugins are enabled. |
1594 |
1593 |
1595 \item |
1594 \item |
1596 The @{text nonexhaustive} option indicates that the functions are not |
1595 The \<open>nonexhaustive\<close> option indicates that the functions are not |
1597 necessarily specified for all constructors. It can be used to suppress the |
1596 necessarily specified for all constructors. It can be used to suppress the |
1598 warning that is normally emitted when some constructors are missing. |
1597 warning that is normally emitted when some constructors are missing. |
1599 |
1598 |
1600 \item |
1599 \item |
1601 The @{text transfer} option indicates that an unconditional transfer rule |
1600 The \<open>transfer\<close> option indicates that an unconditional transfer rule |
1602 should be generated and proved @{text "by transfer_prover"}. The |
1601 should be generated and proved \<open>by transfer_prover\<close>. The |
1603 @{text "[transfer_rule]"} attribute is set on the generated theorem. |
1602 \<open>[transfer_rule]\<close> attribute is set on the generated theorem. |
1604 \end{itemize} |
1603 \end{itemize} |
1605 |
1604 |
1606 %%% TODO: elaborate on format of the equations |
1605 %%% TODO: elaborate on format of the equations |
1607 %%% TODO: elaborate on mutual and nested-to-mutual |
1606 %%% TODO: elaborate on mutual and nested-to-mutual |
1608 \<close> |
1607 \<close> |
1621 for @{const tfold}): |
1620 for @{const tfold}): |
1622 |
1621 |
1623 \begin{indentblock} |
1622 \begin{indentblock} |
1624 \begin{description} |
1623 \begin{description} |
1625 |
1624 |
1626 \item[@{text "f."}\hthm{simps} @{text "[simp, code]"}\rm:] ~ \\ |
1625 \item[\<open>f.\<close>\hthm{simps} \<open>[simp, code]\<close>\rm:] ~ \\ |
1627 @{thm tfold.simps(1)[no_vars]} \\ |
1626 @{thm tfold.simps(1)[no_vars]} \\ |
1628 @{thm tfold.simps(2)[no_vars]} \\ |
1627 @{thm tfold.simps(2)[no_vars]} \\ |
1629 The @{text "[code]"} attribute is set by the @{text code} plugin |
1628 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
1630 (Section~\ref{ssec:code-generator}). |
1629 (Section~\ref{ssec:code-generator}). |
1631 |
1630 |
1632 \item[@{text "f."}\hthm{transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1631 \item[\<open>f.\<close>\hthm{transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
1633 @{thm tfold.transfer[no_vars]} \\ |
1632 @{thm tfold.transfer[no_vars]} \\ |
1634 This theorem is generated by the @{text transfer} plugin |
1633 This theorem is generated by the \<open>transfer\<close> plugin |
1635 (Section~\ref{ssec:transfer}) for functions declared with the @{text transfer} |
1634 (Section~\ref{ssec:transfer}) for functions declared with the \<open>transfer\<close> |
1636 option enabled. |
1635 option enabled. |
1637 |
1636 |
1638 \item[@{text "f."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
1637 \item[\<open>f.\<close>\hthm{induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm:] ~ \\ |
1639 This induction rule is generated for nested-as-mutual recursive functions |
1638 This induction rule is generated for nested-as-mutual recursive functions |
1640 (Section~\ref{sssec:primrec-nested-as-mutual-recursion}). |
1639 (Section~\ref{sssec:primrec-nested-as-mutual-recursion}). |
1641 |
1640 |
1642 \item[@{text "f\<^sub>1_\<dots>_f\<^sub>m."}\hthm{induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n]"}\rm:] ~ \\ |
1641 \item[\<open>f\<^sub>1_\<dots>_f\<^sub>m.\<close>\hthm{induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n]\<close>\rm:] ~ \\ |
1643 This induction rule is generated for nested-as-mutual recursive functions |
1642 This induction rule is generated for nested-as-mutual recursive functions |
1644 (Section~\ref{sssec:primrec-nested-as-mutual-recursion}). Given $m > 1$ mutually |
1643 (Section~\ref{sssec:primrec-nested-as-mutual-recursion}). Given $m > 1$ mutually |
1645 recursive functions, this rule can be used to prove $m$ properties |
1644 recursive functions, this rule can be used to prove $m$ properties |
1646 simultaneously. |
1645 simultaneously. |
1647 |
1646 |
1656 |
1655 |
1657 subsection \<open>Recursive Default Values for Selectors |
1656 subsection \<open>Recursive Default Values for Selectors |
1658 \label{ssec:primrec-recursive-default-values-for-selectors}\<close> |
1657 \label{ssec:primrec-recursive-default-values-for-selectors}\<close> |
1659 |
1658 |
1660 text \<open> |
1659 text \<open> |
1661 A datatype selector @{text un_D} can have a default value for each constructor |
1660 A datatype selector \<open>un_D\<close> can have a default value for each constructor |
1662 on which it is not otherwise specified. Occasionally, it is useful to have the |
1661 on which it is not otherwise specified. Occasionally, it is useful to have the |
1663 default value be defined recursively. This leads to a chicken-and-egg |
1662 default value be defined recursively. This leads to a chicken-and-egg |
1664 situation, because the datatype is not introduced yet at the moment when the |
1663 situation, because the datatype is not introduced yet at the moment when the |
1665 selectors are introduced. Of course, we can always define the selectors |
1664 selectors are introduced. Of course, we can always define the selectors |
1666 manually afterward, but we then have to state and prove all the characteristic |
1665 manually afterward, but we then have to state and prove all the characteristic |
1671 |
1670 |
1672 \begin{enumerate} |
1671 \begin{enumerate} |
1673 \setlength{\itemsep}{0pt} |
1672 \setlength{\itemsep}{0pt} |
1674 |
1673 |
1675 \item |
1674 \item |
1676 Introduce a fully unspecified constant @{text "un_D\<^sub>0 :: 'a"} using |
1675 Introduce a fully unspecified constant \<open>un_D\<^sub>0 :: 'a\<close> using |
1677 @{command consts}. |
1676 @{command consts}. |
1678 |
1677 |
1679 \item |
1678 \item |
1680 Define the datatype, specifying @{text "un_D\<^sub>0"} as the selector's default |
1679 Define the datatype, specifying \<open>un_D\<^sub>0\<close> as the selector's default |
1681 value. |
1680 value. |
1682 |
1681 |
1683 \item |
1682 \item |
1684 Define the behavior of @{text "un_D\<^sub>0"} on values of the newly introduced |
1683 Define the behavior of \<open>un_D\<^sub>0\<close> on values of the newly introduced |
1685 datatype using the \keyw{overloading} command. |
1684 datatype using the \keyw{overloading} command. |
1686 |
1685 |
1687 \item |
1686 \item |
1688 Derive the desired equation on @{text un_D} from the characteristic equations |
1687 Derive the desired equation on \<open>un_D\<close> from the characteristic equations |
1689 for @{text "un_D\<^sub>0"}. |
1688 for \<open>un_D\<^sub>0\<close>. |
1690 \end{enumerate} |
1689 \end{enumerate} |
1691 |
1690 |
1692 \noindent |
1691 \noindent |
1693 The following example illustrates this procedure: |
1692 The following example illustrates this procedure: |
1694 \<close> |
1693 \<close> |
1735 \begin{itemize} |
1734 \begin{itemize} |
1736 \setlength{\itemsep}{0pt} |
1735 \setlength{\itemsep}{0pt} |
1737 |
1736 |
1738 \item \emph{Some theorems have different names.} |
1737 \item \emph{Some theorems have different names.} |
1739 For $m > 1$ mutually recursive functions, |
1738 For $m > 1$ mutually recursive functions, |
1740 @{text "f\<^sub>1_\<dots>_f\<^sub>m.simps"} has been broken down into separate |
1739 \<open>f\<^sub>1_\<dots>_f\<^sub>m.simps\<close> has been broken down into separate |
1741 subcollections @{text "f\<^sub>i.simps"}. |
1740 subcollections \<open>f\<^sub>i.simps\<close>. |
1742 \end{itemize} |
1741 \end{itemize} |
1743 \<close> |
1742 \<close> |
1744 |
1743 |
1745 |
1744 |
1746 section \<open>Defining Codatatypes |
1745 section \<open>Defining Codatatypes |
1779 where |
1778 where |
1780 "ltl LNil = LNil" |
1779 "ltl LNil = LNil" |
1781 |
1780 |
1782 text \<open> |
1781 text \<open> |
1783 \noindent |
1782 \noindent |
1784 Lazy lists can be infinite, such as @{text "LCons 0 (LCons 0 (\<dots>))"} and |
1783 Lazy lists can be infinite, such as \<open>LCons 0 (LCons 0 (\<dots>))\<close> and |
1785 @{text "LCons 0 (LCons 1 (LCons 2 (\<dots>)))"}. Here is a related type, that of |
1784 \<open>LCons 0 (LCons 1 (LCons 2 (\<dots>)))\<close>. Here is a related type, that of |
1786 infinite streams: |
1785 infinite streams: |
1787 \<close> |
1786 \<close> |
1788 |
1787 |
1789 codatatype (sset: 'a) stream = |
1788 codatatype (sset: 'a) stream = |
1790 SCons (shd: 'a) (stl: "'a stream") |
1789 SCons (shd: 'a) (stl: "'a stream") |
1800 |
1799 |
1801 codatatype enat = EZero | ESucc enat |
1800 codatatype enat = EZero | ESucc enat |
1802 |
1801 |
1803 text \<open> |
1802 text \<open> |
1804 \noindent |
1803 \noindent |
1805 This type has exactly one infinite element, @{text "ESucc (ESucc (ESucc (\<dots>)))"}, |
1804 This type has exactly one infinite element, \<open>ESucc (ESucc (ESucc (\<dots>)))\<close>, |
1806 that represents $\infty$. In addition, it has finite values of the form |
1805 that represents $\infty$. In addition, it has finite values of the form |
1807 @{text "ESucc (\<dots> (ESucc EZero)\<dots>)"}. |
1806 \<open>ESucc (\<dots> (ESucc EZero)\<dots>)\<close>. |
1808 |
1807 |
1809 Here is an example with many constructors: |
1808 Here is an example with many constructors: |
1810 \<close> |
1809 \<close> |
1811 |
1810 |
1812 codatatype 'a process = |
1811 codatatype 'a process = |
1859 subsubsection \<open>\keyw{codatatype} |
1858 subsubsection \<open>\keyw{codatatype} |
1860 \label{sssec:codatatype}\<close> |
1859 \label{sssec:codatatype}\<close> |
1861 |
1860 |
1862 text \<open> |
1861 text \<open> |
1863 \begin{matharray}{rcl} |
1862 \begin{matharray}{rcl} |
1864 @{command_def "codatatype"} & : & @{text "local_theory \<rightarrow> local_theory"} |
1863 @{command_def "codatatype"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
1865 \end{matharray} |
1864 \end{matharray} |
1866 |
1865 |
1867 @{rail \<open> |
1866 @{rail \<open> |
1868 @@{command codatatype} target? @{syntax dt_options}? @{syntax dt_spec} |
1867 @@{command codatatype} target? @{syntax dt_options}? @{syntax dt_spec} |
1869 \<close>} |
1868 \<close>} |
1870 |
1869 |
1871 \medskip |
1870 \medskip |
1872 |
1871 |
1873 \noindent |
1872 \noindent |
1874 Definitions of codatatypes have almost exactly the same syntax as for datatypes |
1873 Definitions of codatatypes have almost exactly the same syntax as for datatypes |
1875 (Section~\ref{ssec:datatype-command-syntax}). The @{text "discs_sels"} option |
1874 (Section~\ref{ssec:datatype-command-syntax}). The \<open>discs_sels\<close> option |
1876 is superfluous because discriminators and selectors are always generated for |
1875 is superfluous because discriminators and selectors are always generated for |
1877 codatatypes. |
1876 codatatypes. |
1878 \<close> |
1877 \<close> |
1879 |
1878 |
1880 |
1879 |
1881 subsection \<open>Generated Constants |
1880 subsection \<open>Generated Constants |
1882 \label{ssec:codatatype-generated-constants}\<close> |
1881 \label{ssec:codatatype-generated-constants}\<close> |
1883 |
1882 |
1884 text \<open> |
1883 text \<open> |
1885 Given a codatatype @{text "('a\<^sub>1, \<dots>, 'a\<^sub>m) t"} |
1884 Given a codatatype \<open>('a\<^sub>1, \<dots>, 'a\<^sub>m) t\<close> |
1886 with $m > 0$ live type variables and $n$ constructors @{text "t.C\<^sub>1"}, |
1885 with $m > 0$ live type variables and $n$ constructors \<open>t.C\<^sub>1\<close>, |
1887 \ldots, @{text "t.C\<^sub>n"}, the same auxiliary constants are generated as for |
1886 \ldots, \<open>t.C\<^sub>n\<close>, the same auxiliary constants are generated as for |
1888 datatypes (Section~\ref{ssec:datatype-generated-constants}), except that the |
1887 datatypes (Section~\ref{ssec:datatype-generated-constants}), except that the |
1889 recursor is replaced by a dual concept: |
1888 recursor is replaced by a dual concept: |
1890 |
1889 |
1891 \medskip |
1890 \medskip |
1892 |
1891 |
1893 \begin{tabular}{@ {}ll@ {}} |
1892 \begin{tabular}{@ {}ll@ {}} |
1894 Corecursor: & |
1893 Corecursor: & |
1895 @{text t.corec_t} |
1894 \<open>t.corec_t\<close> |
1896 \end{tabular} |
1895 \end{tabular} |
1897 \<close> |
1896 \<close> |
1898 |
1897 |
1899 |
1898 |
1900 subsection \<open>Generated Theorems |
1899 subsection \<open>Generated Theorems |
1932 |
1931 |
1933 \begin{indentblock} |
1932 \begin{indentblock} |
1934 \begin{description} |
1933 \begin{description} |
1935 |
1934 |
1936 \item[\begin{tabular}{@ {}l@ {}} |
1935 \item[\begin{tabular}{@ {}l@ {}} |
1937 @{text "t."}\hthm{coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1936 \<open>t.\<close>\hthm{coinduct} \<open>[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
1938 \phantom{@{text "t."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
1937 \phantom{\<open>t.\<close>\hthm{coinduct} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> |
1939 D\<^sub>n, coinduct t]"}\rm: |
1938 D\<^sub>n, coinduct t]\<close>\rm: |
1940 \end{tabular}] ~ \\ |
1939 \end{tabular}] ~ \\ |
1941 @{thm llist.coinduct[no_vars]} |
1940 @{thm llist.coinduct[no_vars]} |
1942 |
1941 |
1943 \item[\begin{tabular}{@ {}l@ {}} |
1942 \item[\begin{tabular}{@ {}l@ {}} |
1944 @{text "t."}\hthm{coinduct_strong} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1943 \<open>t.\<close>\hthm{coinduct_strong} \<open>[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
1945 \phantom{@{text "t."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: |
1944 \phantom{\<open>t.\<close>\hthm{coinduct_strong} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> D\<^sub>n]\<close>\rm: |
1946 \end{tabular}] ~ \\ |
1945 \end{tabular}] ~ \\ |
1947 @{thm llist.coinduct_strong[no_vars]} |
1946 @{thm llist.coinduct_strong[no_vars]} |
1948 |
1947 |
1949 \item[\begin{tabular}{@ {}l@ {}} |
1948 \item[\begin{tabular}{@ {}l@ {}} |
1950 @{text "t."}\hthm{rel_coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1949 \<open>t.\<close>\hthm{rel_coinduct} \<open>[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
1951 \phantom{@{text "t."}\hthm{rel_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
1950 \phantom{\<open>t.\<close>\hthm{rel_coinduct} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> |
1952 D\<^sub>n, coinduct pred]"}\rm: |
1951 D\<^sub>n, coinduct pred]\<close>\rm: |
1953 \end{tabular}] ~ \\ |
1952 \end{tabular}] ~ \\ |
1954 @{thm llist.rel_coinduct[no_vars]} |
1953 @{thm llist.rel_coinduct[no_vars]} |
1955 |
1954 |
1956 \item[\begin{tabular}{@ {}l@ {}} |
1955 \item[\begin{tabular}{@ {}l@ {}} |
1957 @{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]"} \\ |
1956 \<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{coinduct} \<open>[case_names t\<^sub>1 \<dots> t\<^sub>m, case_conclusion D\<^sub>1 \<dots> D\<^sub>n]\<close> \\ |
1958 @{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{coinduct_strong} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1957 \<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{coinduct_strong} \<open>[case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
1959 \phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: \\ |
1958 \phantom{\<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{coinduct_strong} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> D\<^sub>n]\<close>\rm: \\ |
1960 @{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
1959 \<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{rel_coinduct} \<open>[case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
1961 \phantom{@{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{rel_coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> D\<^sub>n]"}\rm: \\ |
1960 \phantom{\<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{rel_coinduct} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> D\<^sub>n]\<close>\rm: \\ |
1962 \end{tabular}] ~ \\ |
1961 \end{tabular}] ~ \\ |
1963 Given $m > 1$ mutually corecursive codatatypes, these coinduction rules can be |
1962 Given $m > 1$ mutually corecursive codatatypes, these coinduction rules can be |
1964 used to prove $m$ properties simultaneously. |
1963 used to prove $m$ properties simultaneously. |
1965 |
1964 |
1966 \item[\begin{tabular}{@ {}l@ {}} |
1965 \item[\begin{tabular}{@ {}l@ {}} |
1967 @{text "t\<^sub>1_\<dots>_t\<^sub>m."}\hthm{set_induct} @{text "[case_names C\<^sub>1 \<dots> C\<^sub>n,"} \\ |
1966 \<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{set_induct} \<open>[case_names C\<^sub>1 \<dots> C\<^sub>n,\<close> \\ |
1968 \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: \\ |
1967 \phantom{\<open>t\<^sub>1_\<dots>_t\<^sub>m.\<close>\hthm{set_induct} \<open>[\<close>}\<open>induct set: set\<^sub>j_t\<^sub>1, \<dots>, induct set: set\<^sub>j_t\<^sub>m]\<close>\rm: \\ |
1969 \end{tabular}] ~ \\ |
1968 \end{tabular}] ~ \\ |
1970 @{thm llist.set_induct[no_vars]} \\ |
1969 @{thm llist.set_induct[no_vars]} \\ |
1971 If $m = 1$, the attribute @{text "[consumes 1]"} is generated as well. |
1970 If $m = 1$, the attribute \<open>[consumes 1]\<close> is generated as well. |
1972 |
1971 |
1973 \item[@{text "t."}\hthm{corec}\rm:] ~ \\ |
1972 \item[\<open>t.\<close>\hthm{corec}\rm:] ~ \\ |
1974 @{thm llist.corec(1)[no_vars]} \\ |
1973 @{thm llist.corec(1)[no_vars]} \\ |
1975 @{thm llist.corec(2)[no_vars]} |
1974 @{thm llist.corec(2)[no_vars]} |
1976 |
1975 |
1977 \item[@{text "t."}\hthm{corec_code} @{text "[code]"}\rm:] ~ \\ |
1976 \item[\<open>t.\<close>\hthm{corec_code} \<open>[code]\<close>\rm:] ~ \\ |
1978 @{thm llist.corec_code[no_vars]} \\ |
1977 @{thm llist.corec_code[no_vars]} \\ |
1979 The @{text "[code]"} attribute is set by the @{text code} plugin |
1978 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
1980 (Section~\ref{ssec:code-generator}). |
1979 (Section~\ref{ssec:code-generator}). |
1981 |
1980 |
1982 \item[@{text "t."}\hthm{corec_disc}\rm:] ~ \\ |
1981 \item[\<open>t.\<close>\hthm{corec_disc}\rm:] ~ \\ |
1983 @{thm llist.corec_disc(1)[no_vars]} \\ |
1982 @{thm llist.corec_disc(1)[no_vars]} \\ |
1984 @{thm llist.corec_disc(2)[no_vars]} |
1983 @{thm llist.corec_disc(2)[no_vars]} |
1985 |
1984 |
1986 \item[@{text "t."}\hthm{corec_disc_iff} @{text "[simp]"}\rm:] ~ \\ |
1985 \item[\<open>t.\<close>\hthm{corec_disc_iff} \<open>[simp]\<close>\rm:] ~ \\ |
1987 @{thm llist.corec_disc_iff(1)[no_vars]} \\ |
1986 @{thm llist.corec_disc_iff(1)[no_vars]} \\ |
1988 @{thm llist.corec_disc_iff(2)[no_vars]} |
1987 @{thm llist.corec_disc_iff(2)[no_vars]} |
1989 |
1988 |
1990 \item[@{text "t."}\hthm{corec_sel} @{text "[simp]"}\rm:] ~ \\ |
1989 \item[\<open>t.\<close>\hthm{corec_sel} \<open>[simp]\<close>\rm:] ~ \\ |
1991 @{thm llist.corec_sel(1)[no_vars]} \\ |
1990 @{thm llist.corec_sel(1)[no_vars]} \\ |
1992 @{thm llist.corec_sel(2)[no_vars]} |
1991 @{thm llist.corec_sel(2)[no_vars]} |
1993 |
1992 |
1994 \item[@{text "t."}\hthm{map_o_corec}\rm:] ~ \\ |
1993 \item[\<open>t.\<close>\hthm{map_o_corec}\rm:] ~ \\ |
1995 @{thm llist.map_o_corec[no_vars]} |
1994 @{thm llist.map_o_corec[no_vars]} |
1996 |
1995 |
1997 \item[@{text "t."}\hthm{corec_transfer} @{text "[transfer_rule]"}\rm:] ~ \\ |
1996 \item[\<open>t.\<close>\hthm{corec_transfer} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
1998 @{thm llist.corec_transfer[no_vars]} \\ |
1997 @{thm llist.corec_transfer[no_vars]} \\ |
1999 The @{text "[transfer_rule]"} attribute is set by the @{text transfer} plugin |
1998 The \<open>[transfer_rule]\<close> attribute is set by the \<open>transfer\<close> plugin |
2000 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
1999 (Section~\ref{ssec:transfer}) for type constructors with no dead type arguments. |
2001 |
2000 |
2002 \end{description} |
2001 \end{description} |
2003 \end{indentblock} |
2002 \end{indentblock} |
2004 |
2003 |
2006 For convenience, @{command codatatype} also provides the following collection: |
2005 For convenience, @{command codatatype} also provides the following collection: |
2007 |
2006 |
2008 \begin{indentblock} |
2007 \begin{indentblock} |
2009 \begin{description} |
2008 \begin{description} |
2010 |
2009 |
2011 \item[@{text "t."}\hthm{simps}] = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.corec_disc_iff} @{text t.corec_sel} \\ |
2010 \item[\<open>t.\<close>\hthm{simps}] = \<open>t.inject\<close> \<open>t.distinct\<close> \<open>t.case\<close> \<open>t.corec_disc_iff\<close> \<open>t.corec_sel\<close> \\ |
2012 @{text t.map} @{text t.rel_inject} @{text t.rel_distinct} @{text t.set} |
2011 \<open>t.map\<close> \<open>t.rel_inject\<close> \<open>t.rel_distinct\<close> \<open>t.set\<close> |
2013 |
2012 |
2014 \end{description} |
2013 \end{description} |
2015 \end{indentblock} |
2014 \end{indentblock} |
2016 \<close> |
2015 \<close> |
2017 |
2016 |
2040 |
2039 |
2041 \abovedisplayskip=.5\abovedisplayskip |
2040 \abovedisplayskip=.5\abovedisplayskip |
2042 \belowdisplayskip=.5\belowdisplayskip |
2041 \belowdisplayskip=.5\belowdisplayskip |
2043 |
2042 |
2044 \item The \emph{destructor view} specifies $f$ by implications of the form |
2043 \item The \emph{destructor view} specifies $f$ by implications of the form |
2045 \[@{text "\<dots> \<Longrightarrow> is_C\<^sub>j (f x\<^sub>1 \<dots> x\<^sub>n)"}\] and |
2044 \[\<open>\<dots> \<Longrightarrow> is_C\<^sub>j (f x\<^sub>1 \<dots> x\<^sub>n)\<close>\] and |
2046 equations of the form |
2045 equations of the form |
2047 \[@{text "un_C\<^sub>ji (f x\<^sub>1 \<dots> x\<^sub>n) = \<dots>"}\] |
2046 \[\<open>un_C\<^sub>ji (f x\<^sub>1 \<dots> x\<^sub>n) = \<dots>\<close>\] |
2048 This style is popular in the coalgebraic literature. |
2047 This style is popular in the coalgebraic literature. |
2049 |
2048 |
2050 \item The \emph{constructor view} specifies $f$ by equations of the form |
2049 \item The \emph{constructor view} specifies $f$ by equations of the form |
2051 \[@{text "\<dots> \<Longrightarrow> f x\<^sub>1 \<dots> x\<^sub>n = C\<^sub>j \<dots>"}\] |
2050 \[\<open>\<dots> \<Longrightarrow> f x\<^sub>1 \<dots> x\<^sub>n = C\<^sub>j \<dots>\<close>\] |
2052 This style is often more concise than the previous one. |
2051 This style is often more concise than the previous one. |
2053 |
2052 |
2054 \item The \emph{code view} specifies $f$ by a single equation of the form |
2053 \item The \emph{code view} specifies $f$ by a single equation of the form |
2055 \[@{text "f x\<^sub>1 \<dots> x\<^sub>n = \<dots>"}\] |
2054 \[\<open>f x\<^sub>1 \<dots> x\<^sub>n = \<dots>\<close>\] |
2056 with restrictions on the format of the right-hand side. Lazy functional |
2055 with restrictions on the format of the right-hand side. Lazy functional |
2057 programming languages such as Haskell support a generalized version of this |
2056 programming languages such as Haskell support a generalized version of this |
2058 style. |
2057 style. |
2059 \end{itemize} |
2058 \end{itemize} |
2060 |
2059 |
2098 |
2097 |
2099 text \<open> |
2098 text \<open> |
2100 \noindent |
2099 \noindent |
2101 The constructor ensures that progress is made---i.e., the function is |
2100 The constructor ensures that progress is made---i.e., the function is |
2102 \emph{productive}. The above functions compute the infinite lazy list or stream |
2101 \emph{productive}. The above functions compute the infinite lazy list or stream |
2103 @{text "[x, g x, g (g x), \<dots>]"}. Productivity guarantees that prefixes |
2102 \<open>[x, g x, g (g x), \<dots>]\<close>. Productivity guarantees that prefixes |
2104 @{text "[x, g x, g (g x), \<dots>, (g ^^ k) x]"} of arbitrary finite length |
2103 \<open>[x, g x, g (g x), \<dots>, (g ^^ k) x]\<close> of arbitrary finite length |
2105 @{text k} can be computed by unfolding the code equation a finite number of |
2104 \<open>k\<close> can be computed by unfolding the code equation a finite number of |
2106 times. |
2105 times. |
2107 |
2106 |
2108 Corecursive functions construct codatatype values, but nothing prevents them |
2107 Corecursive functions construct codatatype values, but nothing prevents them |
2109 from also consuming such values. The following function drops every second |
2108 from also consuming such values. The following function drops every second |
2110 element in a stream: |
2109 element in a stream: |
2113 primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
2112 primcorec every_snd :: "'a stream \<Rightarrow> 'a stream" where |
2114 "every_snd s = SCons (shd s) (stl (stl s))" |
2113 "every_snd s = SCons (shd s) (stl (stl s))" |
2115 |
2114 |
2116 text \<open> |
2115 text \<open> |
2117 \noindent |
2116 \noindent |
2118 Constructs such as @{text "let"}--@{text "in"}, @{text |
2117 Constructs such as \<open>let\<close>--\<open>in\<close>, \<open>if\<close>--\<open>then\<close>--\<open>else\<close>, and \<open>case\<close>--\<open>of\<close> may |
2119 "if"}--@{text "then"}--@{text "else"}, and @{text "case"}--@{text "of"} may |
|
2120 appear around constructors that guard corecursive calls: |
2118 appear around constructors that guard corecursive calls: |
2121 \<close> |
2119 \<close> |
2122 |
2120 |
2123 primcorec lapp :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
2121 primcorec lapp :: "'a llist \<Rightarrow> 'a llist \<Rightarrow> 'a llist" where |
2124 "lapp xs ys = |
2122 "lapp xs ys = |
2126 LNil \<Rightarrow> ys |
2124 LNil \<Rightarrow> ys |
2127 | LCons x xs' \<Rightarrow> LCons x (lapp xs' ys))" |
2125 | LCons x xs' \<Rightarrow> LCons x (lapp xs' ys))" |
2128 |
2126 |
2129 text \<open> |
2127 text \<open> |
2130 \noindent |
2128 \noindent |
2131 For technical reasons, @{text "case"}--@{text "of"} is only supported for |
2129 For technical reasons, \<open>case\<close>--\<open>of\<close> is only supported for |
2132 case distinctions on (co)datatypes that provide discriminators and selectors. |
2130 case distinctions on (co)datatypes that provide discriminators and selectors. |
2133 |
2131 |
2134 Pattern matching is not supported by @{command primcorec}. Fortunately, it is |
2132 Pattern matching is not supported by @{command primcorec}. Fortunately, it is |
2135 easy to generate pattern-maching equations using the @{command simps_of_case} |
2133 easy to generate pattern-maching equations using the @{command simps_of_case} |
2136 command provided by the theory \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close>. |
2134 command provided by the theory \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close>. |
2153 "infty = ESucc infty" |
2151 "infty = ESucc infty" |
2154 |
2152 |
2155 text \<open> |
2153 text \<open> |
2156 \noindent |
2154 \noindent |
2157 The example below constructs a pseudorandom process value. It takes a stream of |
2155 The example below constructs a pseudorandom process value. It takes a stream of |
2158 actions (@{text s}), a pseudorandom function generator (@{text f}), and a |
2156 actions (\<open>s\<close>), a pseudorandom function generator (\<open>f\<close>), and a |
2159 pseudorandom seed (@{text n}): |
2157 pseudorandom seed (\<open>n\<close>): |
2160 \<close> |
2158 \<close> |
2161 |
2159 |
2162 (*<*) |
2160 (*<*) |
2163 context early |
2161 context early |
2164 begin |
2162 begin |
2208 \label{sssec:primcorec-nested-corecursion}\<close> |
2206 \label{sssec:primcorec-nested-corecursion}\<close> |
2209 |
2207 |
2210 text \<open> |
2208 text \<open> |
2211 The next pair of examples generalize the @{const literate} and @{const siterate} |
2209 The next pair of examples generalize the @{const literate} and @{const siterate} |
2212 functions (Section~\ref{sssec:primcorec-nested-corecursion}) to possibly |
2210 functions (Section~\ref{sssec:primcorec-nested-corecursion}) to possibly |
2213 infinite trees in which subnodes are organized either as a lazy list (@{text |
2211 infinite trees in which subnodes are organized either as a lazy list (\<open>tree\<^sub>i\<^sub>i\<close>) or as a finite set (\<open>tree\<^sub>i\<^sub>s\<close>). They rely on the map functions of |
2214 tree\<^sub>i\<^sub>i}) or as a finite set (@{text tree\<^sub>i\<^sub>s}). They rely on the map functions of |
|
2215 the nesting type constructors to lift the corecursive calls: |
2212 the nesting type constructors to lift the corecursive calls: |
2216 \<close> |
2213 \<close> |
2217 |
2214 |
2218 primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
2215 primcorec iterate\<^sub>i\<^sub>i :: "('a \<Rightarrow> 'a llist) \<Rightarrow> 'a \<Rightarrow> 'a tree\<^sub>i\<^sub>i" where |
2219 "iterate\<^sub>i\<^sub>i g x = Node\<^sub>i\<^sub>i x (lmap (iterate\<^sub>i\<^sub>i g) (g x))" |
2216 "iterate\<^sub>i\<^sub>i g x = Node\<^sub>i\<^sub>i x (lmap (iterate\<^sub>i\<^sub>i g) (g x))" |
2250 Node\<^sub>i\<^sub>i (shd s) (LCons (tree\<^sub>i\<^sub>i_of_stream (stl s)) LNil)" |
2247 Node\<^sub>i\<^sub>i (shd s) (LCons (tree\<^sub>i\<^sub>i_of_stream (stl s)) LNil)" |
2251 |
2248 |
2252 text \<open> |
2249 text \<open> |
2253 The next example illustrates corecursion through functions, which is a bit |
2250 The next example illustrates corecursion through functions, which is a bit |
2254 special. Deterministic finite automata (DFAs) are traditionally defined as |
2251 special. Deterministic finite automata (DFAs) are traditionally defined as |
2255 5-tuples @{text "(Q, \<Sigma>, \<delta>, q\<^sub>0, F)"}, where @{text Q} is a finite set of states, |
2252 5-tuples \<open>(Q, \<Sigma>, \<delta>, q\<^sub>0, F)\<close>, where \<open>Q\<close> is a finite set of states, |
2256 @{text \<Sigma>} is a finite alphabet, @{text \<delta>} is a transition function, @{text q\<^sub>0} |
2253 \<open>\<Sigma>\<close> is a finite alphabet, \<open>\<delta>\<close> is a transition function, \<open>q\<^sub>0\<close> |
2257 is an initial state, and @{text F} is a set of final states. The following |
2254 is an initial state, and \<open>F\<close> is a set of final states. The following |
2258 function translates a DFA into a state machine: |
2255 function translates a DFA into a state machine: |
2259 \<close> |
2256 \<close> |
2260 |
2257 |
2261 primcorec (*<*)(in early) (*>*)sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2258 primcorec (*<*)(in early) (*>*)sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2262 "sm_of_dfa \<delta> F q = SM (q \<in> F) (sm_of_dfa \<delta> F \<circ> \<delta> q)" |
2259 "sm_of_dfa \<delta> F q = SM (q \<in> F) (sm_of_dfa \<delta> F \<circ> \<delta> q)" |
2263 |
2260 |
2264 text \<open> |
2261 text \<open> |
2265 \noindent |
2262 \noindent |
2266 The map function for the function type (@{text \<Rightarrow>}) is composition |
2263 The map function for the function type (\<open>\<Rightarrow>\<close>) is composition |
2267 (@{text "(\<circ>)"}). For convenience, corecursion through functions can |
2264 (\<open>(\<circ>)\<close>). For convenience, corecursion through functions can |
2268 also be expressed using $\lambda$-abstractions and function application rather |
2265 also be expressed using $\lambda$-abstractions and function application rather |
2269 than through composition. For example: |
2266 than through composition. For example: |
2270 \<close> |
2267 \<close> |
2271 |
2268 |
2272 primcorec sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2269 primcorec sm_of_dfa :: "('q \<Rightarrow> 'a \<Rightarrow> 'q) \<Rightarrow> 'q set \<Rightarrow> 'q \<Rightarrow> 'a sm" where |
2341 \noindent |
2338 \noindent |
2342 Coinduction rules are generated as |
2339 Coinduction rules are generated as |
2343 @{thm [source] iterate\<^sub>i\<^sub>i.coinduct}, |
2340 @{thm [source] iterate\<^sub>i\<^sub>i.coinduct}, |
2344 @{thm [source] iterates\<^sub>i\<^sub>i.coinduct}, and |
2341 @{thm [source] iterates\<^sub>i\<^sub>i.coinduct}, and |
2345 @{thm [source] iterate\<^sub>i\<^sub>i_iterates\<^sub>i\<^sub>i.coinduct} |
2342 @{thm [source] iterate\<^sub>i\<^sub>i_iterates\<^sub>i\<^sub>i.coinduct} |
2346 and analogously for @{text coinduct_strong}. These rules and the |
2343 and analogously for \<open>coinduct_strong\<close>. These rules and the |
2347 underlying corecursors are generated dynamically and are kept in a cache |
2344 underlying corecursors are generated dynamically and are kept in a cache |
2348 to speed up subsequent definitions. |
2345 to speed up subsequent definitions. |
2349 \<close> |
2346 \<close> |
2350 |
2347 |
2351 (*<*) |
2348 (*<*) |
2416 @{term "n mod (4::int) \<noteq> 2"}. |
2413 @{term "n mod (4::int) \<noteq> 2"}. |
2417 The price to pay for this elegance is that we must discharge exclusiveness proof |
2414 The price to pay for this elegance is that we must discharge exclusiveness proof |
2418 obligations, one for each pair of conditions |
2415 obligations, one for each pair of conditions |
2419 @{term "(n mod (4::int) = i, n mod (4::int) = j)"} |
2416 @{term "(n mod (4::int) = i, n mod (4::int) = j)"} |
2420 with @{term "i < j"}. If we prefer not to discharge any obligations, we can |
2417 with @{term "i < j"}. If we prefer not to discharge any obligations, we can |
2421 enable the @{text "sequential"} option. This pushes the problem to the users of |
2418 enable the \<open>sequential\<close> option. This pushes the problem to the users of |
2422 the generated properties. |
2419 the generated properties. |
2423 %Here are more examples to conclude: |
2420 %Here are more examples to conclude: |
2424 \<close> |
2421 \<close> |
2425 |
2422 |
2426 |
2423 |
2433 (*>*) |
2430 (*>*) |
2434 |
2431 |
2435 text \<open> |
2432 text \<open> |
2436 The destructor view is in many respects dual to the constructor view. Conditions |
2433 The destructor view is in many respects dual to the constructor view. Conditions |
2437 determine which constructor to choose, and these conditions are interpreted |
2434 determine which constructor to choose, and these conditions are interpreted |
2438 sequentially or not depending on the @{text "sequential"} option. |
2435 sequentially or not depending on the \<open>sequential\<close> option. |
2439 Consider the following examples: |
2436 Consider the following examples: |
2440 \<close> |
2437 \<close> |
2441 |
2438 |
2442 primcorec literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
2439 primcorec literate :: "('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a llist" where |
2443 "\<not> lnull (literate _ x)" |
2440 "\<not> lnull (literate _ x)" |
2515 | "left (random_process s f n) = random_process (every_snd s) f (f n)" |
2512 | "left (random_process s f n) = random_process (every_snd s) f (f n)" |
2516 | "right (random_process s f n) = random_process (every_snd (stl s)) f (f n)" |
2513 | "right (random_process s f n) = random_process (every_snd (stl s)) f (f n)" |
2517 |
2514 |
2518 text \<open> |
2515 text \<open> |
2519 \noindent |
2516 \noindent |
2520 Using the @{text "of"} keyword, different equations are specified for @{const |
2517 Using the \<open>of\<close> keyword, different equations are specified for @{const |
2521 cont} depending on which constructor is selected. |
2518 cont} depending on which constructor is selected. |
2522 |
2519 |
2523 Here are more examples to conclude: |
2520 Here are more examples to conclude: |
2524 \<close> |
2521 \<close> |
2525 |
2522 |
2547 subsubsection \<open>\keyw{primcorec} and \keyw{primcorecursive} |
2544 subsubsection \<open>\keyw{primcorec} and \keyw{primcorecursive} |
2548 \label{sssec:primcorecursive-and-primcorec}\<close> |
2545 \label{sssec:primcorecursive-and-primcorec}\<close> |
2549 |
2546 |
2550 text \<open> |
2547 text \<open> |
2551 \begin{matharray}{rcl} |
2548 \begin{matharray}{rcl} |
2552 @{command_def "primcorec"} & : & @{text "local_theory \<rightarrow> local_theory"} \\ |
2549 @{command_def "primcorec"} & : & \<open>local_theory \<rightarrow> local_theory\<close> \\ |
2553 @{command_def "primcorecursive"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
2550 @{command_def "primcorecursive"} & : & \<open>local_theory \<rightarrow> proof(prove)\<close> |
2554 \end{matharray} |
2551 \end{matharray} |
2555 |
2552 |
2556 @{rail \<open> |
2553 @{rail \<open> |
2557 (@@{command primcorec} | @@{command primcorecursive}) target? \<newline> |
2554 (@@{command primcorec} | @@{command primcorecursive}) target? \<newline> |
2558 @{syntax pcr_options}? fixes @'where' (@{syntax pcr_formula} + '|') |
2555 @{syntax pcr_options}? fixes @'where' (@{syntax pcr_formula} + '|') |
2578 |
2575 |
2579 \begin{itemize} |
2576 \begin{itemize} |
2580 \setlength{\itemsep}{0pt} |
2577 \setlength{\itemsep}{0pt} |
2581 |
2578 |
2582 \item |
2579 \item |
2583 The @{text plugins} option indicates which plugins should be enabled |
2580 The \<open>plugins\<close> option indicates which plugins should be enabled |
2584 (@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
2581 (\<open>only\<close>) or disabled (\<open>del\<close>). By default, all plugins are enabled. |
2585 |
2582 |
2586 \item |
2583 \item |
2587 The @{text sequential} option indicates that the conditions in specifications |
2584 The \<open>sequential\<close> option indicates that the conditions in specifications |
2588 expressed using the constructor or destructor view are to be interpreted |
2585 expressed using the constructor or destructor view are to be interpreted |
2589 sequentially. |
2586 sequentially. |
2590 |
2587 |
2591 \item |
2588 \item |
2592 The @{text exhaustive} option indicates that the conditions in specifications |
2589 The \<open>exhaustive\<close> option indicates that the conditions in specifications |
2593 expressed using the constructor or destructor view cover all possible cases. |
2590 expressed using the constructor or destructor view cover all possible cases. |
2594 This generally gives rise to an additional proof obligation. |
2591 This generally gives rise to an additional proof obligation. |
2595 |
2592 |
2596 \item |
2593 \item |
2597 The @{text transfer} option indicates that an unconditional transfer rule |
2594 The \<open>transfer\<close> option indicates that an unconditional transfer rule |
2598 should be generated and proved @{text "by transfer_prover"}. The |
2595 should be generated and proved \<open>by transfer_prover\<close>. The |
2599 @{text "[transfer_rule]"} attribute is set on the generated theorem. |
2596 \<open>[transfer_rule]\<close> attribute is set on the generated theorem. |
2600 \end{itemize} |
2597 \end{itemize} |
2601 |
2598 |
2602 The @{command primcorec} command is an abbreviation for @{command |
2599 The @{command primcorec} command is an abbreviation for @{command |
2603 primcorecursive} with @{text "by auto?"} to discharge any emerging proof |
2600 primcorecursive} with \<open>by auto?\<close> to discharge any emerging proof |
2604 obligations. |
2601 obligations. |
2605 |
2602 |
2606 %%% TODO: elaborate on format of the propositions |
2603 %%% TODO: elaborate on format of the propositions |
2607 %%% TODO: elaborate on mutual and nested-to-mutual |
2604 %%% TODO: elaborate on mutual and nested-to-mutual |
2608 \<close> |
2605 \<close> |
2616 following properties (listed for @{const literate}): |
2613 following properties (listed for @{const literate}): |
2617 |
2614 |
2618 \begin{indentblock} |
2615 \begin{indentblock} |
2619 \begin{description} |
2616 \begin{description} |
2620 |
2617 |
2621 \item[@{text "f."}\hthm{code} @{text "[code]"}\rm:] ~ \\ |
2618 \item[\<open>f.\<close>\hthm{code} \<open>[code]\<close>\rm:] ~ \\ |
2622 @{thm literate.code[no_vars]} \\ |
2619 @{thm literate.code[no_vars]} \\ |
2623 The @{text "[code]"} attribute is set by the @{text code} plugin |
2620 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
2624 (Section~\ref{ssec:code-generator}). |
2621 (Section~\ref{ssec:code-generator}). |
2625 |
2622 |
2626 \item[@{text "f."}\hthm{ctr}\rm:] ~ \\ |
2623 \item[\<open>f.\<close>\hthm{ctr}\rm:] ~ \\ |
2627 @{thm literate.ctr[no_vars]} |
2624 @{thm literate.ctr[no_vars]} |
2628 |
2625 |
2629 \item[@{text "f."}\hthm{disc} @{text "[simp, code]"}\rm:] ~ \\ |
2626 \item[\<open>f.\<close>\hthm{disc} \<open>[simp, code]\<close>\rm:] ~ \\ |
2630 @{thm literate.disc[no_vars]} \\ |
2627 @{thm literate.disc[no_vars]} \\ |
2631 The @{text "[code]"} attribute is set by the @{text code} plugin |
2628 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
2632 (Section~\ref{ssec:code-generator}). The @{text "[simp]"} attribute is set only |
2629 (Section~\ref{ssec:code-generator}). The \<open>[simp]\<close> attribute is set only |
2633 for functions for which @{text f.disc_iff} is not available. |
2630 for functions for which \<open>f.disc_iff\<close> is not available. |
2634 |
2631 |
2635 \item[@{text "f."}\hthm{disc_iff} @{text "[simp]"}\rm:] ~ \\ |
2632 \item[\<open>f.\<close>\hthm{disc_iff} \<open>[simp]\<close>\rm:] ~ \\ |
2636 @{thm literate.disc_iff[no_vars]} \\ |
2633 @{thm literate.disc_iff[no_vars]} \\ |
2637 This property is generated only for functions declared with the |
2634 This property is generated only for functions declared with the |
2638 @{text exhaustive} option or whose conditions are trivially exhaustive. |
2635 \<open>exhaustive\<close> option or whose conditions are trivially exhaustive. |
2639 |
2636 |
2640 \item[@{text "f."}\hthm{sel} @{text "[simp, code]"}\rm:] ~ \\ |
2637 \item[\<open>f.\<close>\hthm{sel} \<open>[simp, code]\<close>\rm:] ~ \\ |
2641 @{thm literate.disc[no_vars]} \\ |
2638 @{thm literate.disc[no_vars]} \\ |
2642 The @{text "[code]"} attribute is set by the @{text code} plugin |
2639 The \<open>[code]\<close> attribute is set by the \<open>code\<close> plugin |
2643 (Section~\ref{ssec:code-generator}). |
2640 (Section~\ref{ssec:code-generator}). |
2644 |
2641 |
2645 \item[@{text "f."}\hthm{exclude}\rm:] ~ \\ |
2642 \item[\<open>f.\<close>\hthm{exclude}\rm:] ~ \\ |
2646 These properties are missing for @{const literate} because no exclusiveness |
2643 These properties are missing for @{const literate} because no exclusiveness |
2647 proof obligations arose. In general, the properties correspond to the |
2644 proof obligations arose. In general, the properties correspond to the |
2648 discharged proof obligations. |
2645 discharged proof obligations. |
2649 |
2646 |
2650 \item[@{text "f."}\hthm{exhaust}\rm:] ~ \\ |
2647 \item[\<open>f.\<close>\hthm{exhaust}\rm:] ~ \\ |
2651 This property is missing for @{const literate} because no exhaustiveness |
2648 This property is missing for @{const literate} because no exhaustiveness |
2652 proof obligation arose. In general, the property correspond to the discharged |
2649 proof obligation arose. In general, the property correspond to the discharged |
2653 proof obligation. |
2650 proof obligation. |
2654 |
2651 |
2655 \item[\begin{tabular}{@ {}l@ {}} |
2652 \item[\begin{tabular}{@ {}l@ {}} |
2656 @{text "f."}\hthm{coinduct} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
2653 \<open>f.\<close>\hthm{coinduct} \<open>[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
2657 \phantom{@{text "f."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
2654 \phantom{\<open>f.\<close>\hthm{coinduct} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> |
2658 D\<^sub>n]"}\rm: |
2655 D\<^sub>n]\<close>\rm: |
2659 \end{tabular}] ~ \\ |
2656 \end{tabular}] ~ \\ |
2660 This coinduction rule is generated for nested-as-mutual corecursive functions |
2657 This coinduction rule is generated for nested-as-mutual corecursive functions |
2661 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). |
2658 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). |
2662 |
2659 |
2663 \item[\begin{tabular}{@ {}l@ {}} |
2660 \item[\begin{tabular}{@ {}l@ {}} |
2664 @{text "f."}\hthm{coinduct_strong} @{text "[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
2661 \<open>f.\<close>\hthm{coinduct_strong} \<open>[consumes m, case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
2665 \phantom{@{text "f."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
2662 \phantom{\<open>f.\<close>\hthm{coinduct_strong} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> |
2666 D\<^sub>n]"}\rm: |
2663 D\<^sub>n]\<close>\rm: |
2667 \end{tabular}] ~ \\ |
2664 \end{tabular}] ~ \\ |
2668 This coinduction rule is generated for nested-as-mutual corecursive functions |
2665 This coinduction rule is generated for nested-as-mutual corecursive functions |
2669 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). |
2666 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). |
2670 |
2667 |
2671 \item[\begin{tabular}{@ {}l@ {}} |
2668 \item[\begin{tabular}{@ {}l@ {}} |
2672 @{text "f\<^sub>1_\<dots>_f\<^sub>m."}\hthm{coinduct} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
2669 \<open>f\<^sub>1_\<dots>_f\<^sub>m.\<close>\hthm{coinduct} \<open>[case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
2673 \phantom{@{text "f."}\hthm{coinduct} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
2670 \phantom{\<open>f.\<close>\hthm{coinduct} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> |
2674 D\<^sub>n]"}\rm: |
2671 D\<^sub>n]\<close>\rm: |
2675 \end{tabular}] ~ \\ |
2672 \end{tabular}] ~ \\ |
2676 This coinduction rule is generated for nested-as-mutual corecursive functions |
2673 This coinduction rule is generated for nested-as-mutual corecursive functions |
2677 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). Given $m > 1$ |
2674 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). Given $m > 1$ |
2678 mutually corecursive functions, this rule can be used to prove $m$ properties |
2675 mutually corecursive functions, this rule can be used to prove $m$ properties |
2679 simultaneously. |
2676 simultaneously. |
2680 |
2677 |
2681 \item[\begin{tabular}{@ {}l@ {}} |
2678 \item[\begin{tabular}{@ {}l@ {}} |
2682 @{text "f\<^sub>1_\<dots>_f\<^sub>m."}\hthm{coinduct_strong} @{text "[case_names t\<^sub>1 \<dots> t\<^sub>m,"} \\ |
2679 \<open>f\<^sub>1_\<dots>_f\<^sub>m.\<close>\hthm{coinduct_strong} \<open>[case_names t\<^sub>1 \<dots> t\<^sub>m,\<close> \\ |
2683 \phantom{@{text "f."}\hthm{coinduct_strong} @{text "["}}@{text "case_conclusion D\<^sub>1 \<dots> |
2680 \phantom{\<open>f.\<close>\hthm{coinduct_strong} \<open>[\<close>}\<open>case_conclusion D\<^sub>1 \<dots> |
2684 D\<^sub>n]"}\rm: |
2681 D\<^sub>n]\<close>\rm: |
2685 \end{tabular}] ~ \\ |
2682 \end{tabular}] ~ \\ |
2686 This coinduction rule is generated for nested-as-mutual corecursive functions |
2683 This coinduction rule is generated for nested-as-mutual corecursive functions |
2687 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). Given $m > 1$ |
2684 (Section~\ref{sssec:primcorec-nested-as-mutual-corecursion}). Given $m > 1$ |
2688 mutually corecursive functions, this rule can be used to prove $m$ properties |
2685 mutually corecursive functions, this rule can be used to prove $m$ properties |
2689 simultaneously. |
2686 simultaneously. |
2696 provide the following collection: |
2693 provide the following collection: |
2697 |
2694 |
2698 \begin{indentblock} |
2695 \begin{indentblock} |
2699 \begin{description} |
2696 \begin{description} |
2700 |
2697 |
2701 \item[@{text "f."}\hthm{simps}] = @{text f.disc_iff} (or @{text f.disc}) @{text t.sel} |
2698 \item[\<open>f.\<close>\hthm{simps}] = \<open>f.disc_iff\<close> (or \<open>f.disc\<close>) \<open>t.sel\<close> |
2702 |
2699 |
2703 \end{description} |
2700 \end{description} |
2704 \end{indentblock} |
2701 \end{indentblock} |
2705 \<close> |
2702 \<close> |
2706 |
2703 |
2736 |
2733 |
2737 An $n$-ary BNF is a type constructor equipped with a map function |
2734 An $n$-ary BNF is a type constructor equipped with a map function |
2738 (functorial action), $n$ set functions (natural transformations), |
2735 (functorial action), $n$ set functions (natural transformations), |
2739 and an infinite cardinal bound that satisfy certain properties. |
2736 and an infinite cardinal bound that satisfy certain properties. |
2740 For example, @{typ "'a llist"} is a unary BNF. |
2737 For example, @{typ "'a llist"} is a unary BNF. |
2741 Its predicator @{text "llist_all :: |
2738 Its predicator \<open>llist_all :: |
2742 ('a \<Rightarrow> bool) \<Rightarrow> |
2739 ('a \<Rightarrow> bool) \<Rightarrow> |
2743 'a llist \<Rightarrow> bool"} |
2740 'a llist \<Rightarrow> bool\<close> |
2744 extends unary predicates over elements to unary predicates over |
2741 extends unary predicates over elements to unary predicates over |
2745 lazy lists. |
2742 lazy lists. |
2746 Similarly, its relator @{text "llist_all2 :: |
2743 Similarly, its relator \<open>llist_all2 :: |
2747 ('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> |
2744 ('a \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> |
2748 'a llist \<Rightarrow> 'b llist \<Rightarrow> bool"} |
2745 'a llist \<Rightarrow> 'b llist \<Rightarrow> bool\<close> |
2749 extends binary predicates over elements to binary predicates over parallel |
2746 extends binary predicates over elements to binary predicates over parallel |
2750 lazy lists. The cardinal bound limits the number of elements returned by the |
2747 lazy lists. The cardinal bound limits the number of elements returned by the |
2751 set function; it may not depend on the cardinality of @{typ 'a}. |
2748 set function; it may not depend on the cardinality of @{typ 'a}. |
2752 |
2749 |
2753 The type constructors introduced by @{command datatype} and |
2750 The type constructors introduced by @{command datatype} and |
2945 qed |
2942 qed |
2946 |
2943 |
2947 text \<open> |
2944 text \<open> |
2948 The next example declares a BNF axiomatically. This can be convenient for |
2945 The next example declares a BNF axiomatically. This can be convenient for |
2949 reasoning abstractly about an arbitrary BNF. The @{command bnf_axiomatization} |
2946 reasoning abstractly about an arbitrary BNF. The @{command bnf_axiomatization} |
2950 command below introduces a type @{text "('a, 'b, 'c) F"}, three set constants, |
2947 command below introduces a type \<open>('a, 'b, 'c) F\<close>, three set constants, |
2951 a map function, a predicator, a relator, and a nonemptiness witness that depends only on |
2948 a map function, a predicator, a relator, and a nonemptiness witness that depends only on |
2952 @{typ 'a}. The type @{text "'a \<Rightarrow> ('a, 'b, 'c) F"} of the witness can be read |
2949 @{typ 'a}. The type \<open>'a \<Rightarrow> ('a, 'b, 'c) F\<close> of the witness can be read |
2953 as an implication: Given a witness for @{typ 'a}, we can construct a witness for |
2950 as an implication: Given a witness for @{typ 'a}, we can construct a witness for |
2954 @{text "('a, 'b, 'c) F"}. The BNF properties are postulated as axioms. |
2951 \<open>('a, 'b, 'c) F\<close>. The BNF properties are postulated as axioms. |
2955 \<close> |
2952 \<close> |
2956 |
2953 |
2957 bnf_axiomatization (setA: 'a, setB: 'b, setC: 'c) F |
2954 bnf_axiomatization (setA: 'a, setB: 'b, setC: 'c) F |
2958 [wits: "'a \<Rightarrow> ('a, 'b, 'c) F"] |
2955 [wits: "'a \<Rightarrow> ('a, 'b, 'c) F"] |
2959 |
2956 |
2969 subsubsection \<open>\keyw{bnf} |
2966 subsubsection \<open>\keyw{bnf} |
2970 \label{sssec:bnf}\<close> |
2967 \label{sssec:bnf}\<close> |
2971 |
2968 |
2972 text \<open> |
2969 text \<open> |
2973 \begin{matharray}{rcl} |
2970 \begin{matharray}{rcl} |
2974 @{command_def "bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
2971 @{command_def "bnf"} & : & \<open>local_theory \<rightarrow> proof(prove)\<close> |
2975 \end{matharray} |
2972 \end{matharray} |
2976 |
2973 |
2977 @{rail \<open> |
2974 @{rail \<open> |
2978 @@{command bnf} target? (name ':')? type \<newline> |
2975 @@{command bnf} target? (name ':')? type \<newline> |
2979 'map:' term ('sets:' (term +))? 'bd:' term \<newline> |
2976 'map:' term ('sets:' (term +))? 'bd:' term \<newline> |
2992 The syntactic entity \synt{target} can be used to specify a local context, |
2989 The syntactic entity \synt{target} can be used to specify a local context, |
2993 \synt{type} denotes a HOL type, and \synt{term} denotes a HOL term |
2990 \synt{type} denotes a HOL type, and \synt{term} denotes a HOL term |
2994 @{cite "isabelle-isar-ref"}. |
2991 @{cite "isabelle-isar-ref"}. |
2995 |
2992 |
2996 The @{syntax plugins} option indicates which plugins should be enabled |
2993 The @{syntax plugins} option indicates which plugins should be enabled |
2997 (@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
2994 (\<open>only\<close>) or disabled (\<open>del\<close>). By default, all plugins are enabled. |
2998 |
2995 |
2999 %%% TODO: elaborate on proof obligations |
2996 %%% TODO: elaborate on proof obligations |
3000 \<close> |
2997 \<close> |
3001 |
2998 |
3002 subsubsection \<open>\keyw{lift_bnf} |
2999 subsubsection \<open>\keyw{lift_bnf} |
3003 \label{sssec:lift-bnf}\<close> |
3000 \label{sssec:lift-bnf}\<close> |
3004 |
3001 |
3005 text \<open> |
3002 text \<open> |
3006 \begin{matharray}{rcl} |
3003 \begin{matharray}{rcl} |
3007 @{command_def "lift_bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
3004 @{command_def "lift_bnf"} & : & \<open>local_theory \<rightarrow> proof(prove)\<close> |
3008 \end{matharray} |
3005 \end{matharray} |
3009 |
3006 |
3010 @{rail \<open> |
3007 @{rail \<open> |
3011 @@{command lift_bnf} target? lb_options? \<newline> |
3008 @@{command lift_bnf} target? lb_options? \<newline> |
3012 @{syntax tyargs} name wit_terms? \<newline> |
3009 @{syntax tyargs} name wit_terms? \<newline> |
3022 The @{command lift_bnf} command registers as a BNF an existing type (the |
3019 The @{command lift_bnf} command registers as a BNF an existing type (the |
3023 \emph{abstract type}) that was defined as a subtype of a BNF (the \emph{raw |
3020 \emph{abstract type}) that was defined as a subtype of a BNF (the \emph{raw |
3024 type}) using the @{command typedef} command. To achieve this, it lifts the BNF |
3021 type}) using the @{command typedef} command. To achieve this, it lifts the BNF |
3025 structure on the raw type to the abstract type following a @{term |
3022 structure on the raw type to the abstract type following a @{term |
3026 type_definition} theorem. The theorem is usually inferred from the type, but can |
3023 type_definition} theorem. The theorem is usually inferred from the type, but can |
3027 also be explicitly supplied by means of the optional @{text via} clause. In |
3024 also be explicitly supplied by means of the optional \<open>via\<close> clause. In |
3028 addition, custom names for the set functions, the map function, the predicator, and the relator, |
3025 addition, custom names for the set functions, the map function, the predicator, and the relator, |
3029 as well as nonemptiness witnesses can be specified. |
3026 as well as nonemptiness witnesses can be specified. |
3030 |
3027 |
3031 Nonemptiness witnesses are not lifted from the raw type's BNF, as this would be |
3028 Nonemptiness witnesses are not lifted from the raw type's BNF, as this would be |
3032 incomplete. They must be given as terms (on the raw type) and proved to be |
3029 incomplete. They must be given as terms (on the raw type) and proved to be |
3033 witnesses. The command warns about witness types that are present in the raw |
3030 witnesses. The command warns about witness types that are present in the raw |
3034 type's BNF but not supplied by the user. The warning can be disabled by |
3031 type's BNF but not supplied by the user. The warning can be disabled by |
3035 specifying the @{text no_warn_wits} option. |
3032 specifying the \<open>no_warn_wits\<close> option. |
3036 \<close> |
3033 \<close> |
3037 |
3034 |
3038 subsubsection \<open>\keyw{copy_bnf} |
3035 subsubsection \<open>\keyw{copy_bnf} |
3039 \label{sssec:copy-bnf}\<close> |
3036 \label{sssec:copy-bnf}\<close> |
3040 |
3037 |
3041 text \<open> |
3038 text \<open> |
3042 \begin{matharray}{rcl} |
3039 \begin{matharray}{rcl} |
3043 @{command_def "copy_bnf"} & : & @{text "local_theory \<rightarrow> local_theory"} |
3040 @{command_def "copy_bnf"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
3044 \end{matharray} |
3041 \end{matharray} |
3045 |
3042 |
3046 @{rail \<open> |
3043 @{rail \<open> |
3047 @@{command copy_bnf} target? ('(' @{syntax plugins} ')')? \<newline> |
3044 @@{command copy_bnf} target? ('(' @{syntax plugins} ')')? \<newline> |
3048 @{syntax tyargs} name ('via' thm)? @{syntax map_rel_pred}? |
3045 @{syntax tyargs} name ('via' thm)? @{syntax map_rel_pred}? |
3059 subsubsection \<open>\keyw{bnf_axiomatization} |
3056 subsubsection \<open>\keyw{bnf_axiomatization} |
3060 \label{sssec:bnf-axiomatization}\<close> |
3057 \label{sssec:bnf-axiomatization}\<close> |
3061 |
3058 |
3062 text \<open> |
3059 text \<open> |
3063 \begin{matharray}{rcl} |
3060 \begin{matharray}{rcl} |
3064 @{command_def "bnf_axiomatization"} & : & @{text "local_theory \<rightarrow> local_theory"} |
3061 @{command_def "bnf_axiomatization"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
3065 \end{matharray} |
3062 \end{matharray} |
3066 |
3063 |
3067 @{rail \<open> |
3064 @{rail \<open> |
3068 @@{command bnf_axiomatization} target? ('(' @{syntax plugins} ')')? \<newline> |
3065 @@{command bnf_axiomatization} target? ('(' @{syntax plugins} ')')? \<newline> |
3069 @{syntax tyargs}? name @{syntax wit_types}? \<newline> |
3066 @{syntax tyargs}? name @{syntax wit_types}? \<newline> |
3084 (@{typ 'a}, @{typ 'b}, \ldots), \synt{mixfix} denotes the usual parenthesized |
3081 (@{typ 'a}, @{typ 'b}, \ldots), \synt{mixfix} denotes the usual parenthesized |
3085 mixfix notation, and \synt{types} denotes a space-separated list of types |
3082 mixfix notation, and \synt{types} denotes a space-separated list of types |
3086 @{cite "isabelle-isar-ref"}. |
3083 @{cite "isabelle-isar-ref"}. |
3087 |
3084 |
3088 The @{syntax plugins} option indicates which plugins should be enabled |
3085 The @{syntax plugins} option indicates which plugins should be enabled |
3089 (@{text only}) or disabled (@{text del}). By default, all plugins are enabled. |
3086 (\<open>only\<close>) or disabled (\<open>del\<close>). By default, all plugins are enabled. |
3090 |
3087 |
3091 Type arguments are live by default; they can be marked as dead by entering |
3088 Type arguments are live by default; they can be marked as dead by entering |
3092 @{text dead} in front of the type variable (e.g., @{text "(dead 'a)"}) |
3089 \<open>dead\<close> in front of the type variable (e.g., \<open>(dead 'a)\<close>) |
3093 instead of an identifier for the corresponding set function. Witnesses can be |
3090 instead of an identifier for the corresponding set function. Witnesses can be |
3094 specified by their types. Otherwise, the syntax of @{command bnf_axiomatization} |
3091 specified by their types. Otherwise, the syntax of @{command bnf_axiomatization} |
3095 is identical to the left-hand side of a @{command datatype} or |
3092 is identical to the left-hand side of a @{command datatype} or |
3096 @{command codatatype} definition. |
3093 @{command codatatype} definition. |
3097 |
3094 |
3105 subsubsection \<open>\keyw{print_bnfs} |
3102 subsubsection \<open>\keyw{print_bnfs} |
3106 \label{sssec:print-bnfs}\<close> |
3103 \label{sssec:print-bnfs}\<close> |
3107 |
3104 |
3108 text \<open> |
3105 text \<open> |
3109 \begin{matharray}{rcl} |
3106 \begin{matharray}{rcl} |
3110 @{command_def "print_bnfs"} & : & @{text "local_theory \<rightarrow>"} |
3107 @{command_def "print_bnfs"} & : & \<open>local_theory \<rightarrow>\<close> |
3111 \end{matharray} |
3108 \end{matharray} |
3112 |
3109 |
3113 @{rail \<open> |
3110 @{rail \<open> |
3114 @@{command print_bnfs} |
3111 @@{command print_bnfs} |
3115 \<close>} |
3112 \<close>} |
3126 |
3123 |
3127 % * need for this is rare but may arise if you want e.g. to add destructors to |
3124 % * need for this is rare but may arise if you want e.g. to add destructors to |
3128 % a type not introduced by ... |
3125 % a type not introduced by ... |
3129 % |
3126 % |
3130 % * @{command free_constructors} |
3127 % * @{command free_constructors} |
3131 % * @{text plugins}, @{text discs_sels} |
3128 % * \<open>plugins\<close>, \<open>discs_sels\<close> |
3132 % * hack to have both co and nonco view via locale (cf. ext nats) |
3129 % * hack to have both co and nonco view via locale (cf. ext nats) |
3133 \<close> |
3130 \<close> |
3134 |
3131 |
3135 |
3132 |
3136 (* |
3133 (* |
3145 subsubsection \<open>\keyw{free_constructors} |
3142 subsubsection \<open>\keyw{free_constructors} |
3146 \label{sssec:free-constructors}\<close> |
3143 \label{sssec:free-constructors}\<close> |
3147 |
3144 |
3148 text \<open> |
3145 text \<open> |
3149 \begin{matharray}{rcl} |
3146 \begin{matharray}{rcl} |
3150 @{command_def "free_constructors"} & : & @{text "local_theory \<rightarrow> proof(prove)"} |
3147 @{command_def "free_constructors"} & : & \<open>local_theory \<rightarrow> proof(prove)\<close> |
3151 \end{matharray} |
3148 \end{matharray} |
3152 |
3149 |
3153 @{rail \<open> |
3150 @{rail \<open> |
3154 @@{command free_constructors} target? @{syntax dt_options} \<newline> |
3151 @@{command free_constructors} target? @{syntax dt_options} \<newline> |
3155 name 'for' (@{syntax fc_ctor} + '|') \<newline> |
3152 name 'for' (@{syntax fc_ctor} + '|') \<newline> |
3175 \ref{ssec:datatype-command-syntax}~and~\ref{ssec:codatatype-command-syntax}). |
3172 \ref{ssec:datatype-command-syntax}~and~\ref{ssec:codatatype-command-syntax}). |
3176 A constructor is specified by an optional name for the discriminator, the |
3173 A constructor is specified by an optional name for the discriminator, the |
3177 constructor itself (as a term), and a list of optional names for the selectors. |
3174 constructor itself (as a term), and a list of optional names for the selectors. |
3178 |
3175 |
3179 Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems. |
3176 Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems. |
3180 For bootstrapping reasons, the generally useful @{text "[fundef_cong]"} |
3177 For bootstrapping reasons, the generally useful \<open>[fundef_cong]\<close> |
3181 attribute is not set on the generated @{text case_cong} theorem. It can be |
3178 attribute is not set on the generated \<open>case_cong\<close> theorem. It can be |
3182 added manually using \keyw{declare}. |
3179 added manually using \keyw{declare}. |
3183 \<close> |
3180 \<close> |
3184 |
3181 |
3185 |
3182 |
3186 subsubsection \<open>\keyw{simps_of_case} |
3183 subsubsection \<open>\keyw{simps_of_case} |
3187 \label{sssec:simps-of-case}\<close> |
3184 \label{sssec:simps-of-case}\<close> |
3188 |
3185 |
3189 text \<open> |
3186 text \<open> |
3190 \begin{matharray}{rcl} |
3187 \begin{matharray}{rcl} |
3191 @{command_def "simps_of_case"} & : & @{text "local_theory \<rightarrow> local_theory"} |
3188 @{command_def "simps_of_case"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
3192 \end{matharray} |
3189 \end{matharray} |
3193 |
3190 |
3194 @{rail \<open> |
3191 @{rail \<open> |
3195 @@{command simps_of_case} target? (name ':')? \<newline> |
3192 @@{command simps_of_case} target? (name ':')? \<newline> |
3196 (thm + ) (@'splits' ':' (thm + ))? |
3193 (thm + ) (@'splits' ':' (thm + ))? |
3225 subsubsection \<open>\keyw{case_of_simps} |
3222 subsubsection \<open>\keyw{case_of_simps} |
3226 \label{sssec:case-of-simps}\<close> |
3223 \label{sssec:case-of-simps}\<close> |
3227 |
3224 |
3228 text \<open> |
3225 text \<open> |
3229 \begin{matharray}{rcl} |
3226 \begin{matharray}{rcl} |
3230 @{command_def "case_of_simps"} & : & @{text "local_theory \<rightarrow> local_theory"} |
3227 @{command_def "case_of_simps"} & : & \<open>local_theory \<rightarrow> local_theory\<close> |
3231 \end{matharray} |
3228 \end{matharray} |
3232 |
3229 |
3233 @{rail \<open> |
3230 @{rail \<open> |
3234 @@{command case_of_simps} target? (name ':')? \<newline> |
3231 @@{command case_of_simps} target? (name ':')? \<newline> |
3235 (thm + ) |
3232 (thm + ) |
3306 For types, the plugin derives the following properties: |
3303 For types, the plugin derives the following properties: |
3307 |
3304 |
3308 \begin{indentblock} |
3305 \begin{indentblock} |
3309 \begin{description} |
3306 \begin{description} |
3310 |
3307 |
3311 \item[@{text "t."}\hthm{eq.refl} @{text "[code nbe]"}\rm:] ~ \\ |
3308 \item[\<open>t.\<close>\hthm{eq.refl} \<open>[code nbe]\<close>\rm:] ~ \\ |
3312 @{thm list.eq.refl[no_vars]} |
3309 @{thm list.eq.refl[no_vars]} |
3313 |
3310 |
3314 \item[@{text "t."}\hthm{eq.simps} @{text "[code]"}\rm:] ~ \\ |
3311 \item[\<open>t.\<close>\hthm{eq.simps} \<open>[code]\<close>\rm:] ~ \\ |
3315 @{thm list.eq.simps(1)[no_vars]} \\ |
3312 @{thm list.eq.simps(1)[no_vars]} \\ |
3316 @{thm list.eq.simps(2)[no_vars]} \\ |
3313 @{thm list.eq.simps(2)[no_vars]} \\ |
3317 @{thm list.eq.simps(3)[no_vars]} \\ |
3314 @{thm list.eq.simps(3)[no_vars]} \\ |
3318 @{thm list.eq.simps(4)[no_vars]} \\ |
3315 @{thm list.eq.simps(4)[no_vars]} \\ |
3319 @{thm list.eq.simps(5)[no_vars]} \\ |
3316 @{thm list.eq.simps(5)[no_vars]} \\ |
3320 @{thm list.eq.simps(6)[no_vars]} |
3317 @{thm list.eq.simps(6)[no_vars]} |
3321 |
3318 |
3322 \end{description} |
3319 \end{description} |
3323 \end{indentblock} |
3320 \end{indentblock} |
3324 |
3321 |
3325 In addition, the plugin sets the @{text "[code]"} attribute on a number of |
3322 In addition, the plugin sets the \<open>[code]\<close> attribute on a number of |
3326 properties of freely generated types and of (co)recursive functions, as |
3323 properties of freely generated types and of (co)recursive functions, as |
3327 documented in Sections \ref{ssec:datatype-generated-theorems}, |
3324 documented in Sections \ref{ssec:datatype-generated-theorems}, |
3328 \ref{ssec:primrec-generated-theorems}, \ref{ssec:codatatype-generated-theorems}, |
3325 \ref{ssec:primrec-generated-theorems}, \ref{ssec:codatatype-generated-theorems}, |
3329 and~\ref{ssec:primcorec-generated-theorems}. |
3326 and~\ref{ssec:primcorec-generated-theorems}. |
3330 \<close> |
3327 \<close> |
3332 |
3329 |
3333 subsection \<open>Size |
3330 subsection \<open>Size |
3334 \label{ssec:size}\<close> |
3331 \label{ssec:size}\<close> |
3335 |
3332 |
3336 text \<open> |
3333 text \<open> |
3337 For each datatype @{text t}, the \hthm{size} plugin generates a generic size |
3334 For each datatype \<open>t\<close>, the \hthm{size} plugin generates a generic size |
3338 function @{text "t.size_t"} as well as a specific instance |
3335 function \<open>t.size_t\<close> as well as a specific instance |
3339 @{text "size :: t \<Rightarrow> nat"} belonging to the @{text size} type class. The |
3336 \<open>size :: t \<Rightarrow> nat\<close> belonging to the \<open>size\<close> type class. The |
3340 \keyw{fun} command relies on @{const size} to prove termination of recursive |
3337 \keyw{fun} command relies on @{const size} to prove termination of recursive |
3341 functions on datatypes. |
3338 functions on datatypes. |
3342 |
3339 |
3343 The plugin derives the following properties: |
3340 The plugin derives the following properties: |
3344 |
3341 |
3345 \begin{indentblock} |
3342 \begin{indentblock} |
3346 \begin{description} |
3343 \begin{description} |
3347 |
3344 |
3348 \item[@{text "t."}\hthm{size} @{text "[simp, code]"}\rm:] ~ \\ |
3345 \item[\<open>t.\<close>\hthm{size} \<open>[simp, code]\<close>\rm:] ~ \\ |
3349 @{thm list.size(1)[no_vars]} \\ |
3346 @{thm list.size(1)[no_vars]} \\ |
3350 @{thm list.size(2)[no_vars]} \\ |
3347 @{thm list.size(2)[no_vars]} \\ |
3351 @{thm list.size(3)[no_vars]} \\ |
3348 @{thm list.size(3)[no_vars]} \\ |
3352 @{thm list.size(4)[no_vars]} |
3349 @{thm list.size(4)[no_vars]} |
3353 |
3350 |
3354 \item[@{text "t."}\hthm{size_gen}\rm:] ~ \\ |
3351 \item[\<open>t.\<close>\hthm{size_gen}\rm:] ~ \\ |
3355 @{thm list.size_gen(1)[no_vars]} \\ |
3352 @{thm list.size_gen(1)[no_vars]} \\ |
3356 @{thm list.size_gen(2)[no_vars]} |
3353 @{thm list.size_gen(2)[no_vars]} |
3357 |
3354 |
3358 \item[@{text "t."}\hthm{size_gen_o_map}\rm:] ~ \\ |
3355 \item[\<open>t.\<close>\hthm{size_gen_o_map}\rm:] ~ \\ |
3359 @{thm list.size_gen_o_map[no_vars]} |
3356 @{thm list.size_gen_o_map[no_vars]} |
3360 |
3357 |
3361 \item[@{text "t."}\hthm{size_neq}\rm:] ~ \\ |
3358 \item[\<open>t.\<close>\hthm{size_neq}\rm:] ~ \\ |
3362 This property is missing for @{typ "'a list"}. If the @{term size} function |
3359 This property is missing for @{typ "'a list"}. If the @{term size} function |
3363 always evaluates to a non-zero value, this theorem has the form |
3360 always evaluates to a non-zero value, this theorem has the form |
3364 @{prop "\<not> size x = 0"}. |
3361 @{prop "\<not> size x = 0"}. |
3365 |
3362 |
3366 \end{description} |
3363 \end{description} |
3367 \end{indentblock} |
3364 \end{indentblock} |
3368 |
3365 |
3369 The @{text "t.size"} and @{text "t.size_t"} functions generated for datatypes |
3366 The \<open>t.size\<close> and \<open>t.size_t\<close> functions generated for datatypes |
3370 defined by nested recursion through a datatype @{text u} depend on |
3367 defined by nested recursion through a datatype \<open>u\<close> depend on |
3371 @{text "u.size_u"}. |
3368 \<open>u.size_u\<close>. |
3372 |
3369 |
3373 If the recursion is through a non-datatype @{text u} with type arguments |
3370 If the recursion is through a non-datatype \<open>u\<close> with type arguments |
3374 @{text "'a\<^sub>1, \<dots>, 'a\<^sub>m"}, by default @{text u} values are given a size of 0. This |
3371 \<open>'a\<^sub>1, \<dots>, 'a\<^sub>m\<close>, by default \<open>u\<close> values are given a size of 0. This |
3375 can be improved upon by registering a custom size function of type |
3372 can be improved upon by registering a custom size function of type |
3376 @{text "('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat"} using |
3373 \<open>('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat\<close> using |
3377 the ML function @{ML BNF_LFP_Size.register_size} or |
3374 the ML function @{ML BNF_LFP_Size.register_size} or |
3378 @{ML BNF_LFP_Size.register_size_global}. See theory |
3375 @{ML BNF_LFP_Size.register_size_global}. See theory |
3379 \<^file>\<open>~~/src/HOL/Library/Multiset.thy\<close> for an example. |
3376 \<^file>\<open>~~/src/HOL/Library/Multiset.thy\<close> for an example. |
3380 \<close> |
3377 \<close> |
3381 |
3378 |
3383 subsection \<open>Transfer |
3380 subsection \<open>Transfer |
3384 \label{ssec:transfer}\<close> |
3381 \label{ssec:transfer}\<close> |
3385 |
3382 |
3386 text \<open> |
3383 text \<open> |
3387 For each (co)datatype with live type arguments and each manually registered BNF, |
3384 For each (co)datatype with live type arguments and each manually registered BNF, |
3388 the \hthm{transfer} plugin generates a predicator @{text "t.pred_t"} and |
3385 the \hthm{transfer} plugin generates a predicator \<open>t.pred_t\<close> and |
3389 properties that guide the Transfer tool. |
3386 properties that guide the Transfer tool. |
3390 |
3387 |
3391 For types with at least one live type argument and \emph{no dead type |
3388 For types with at least one live type argument and \emph{no dead type |
3392 arguments}, the plugin derives the following properties: |
3389 arguments}, the plugin derives the following properties: |
3393 |
3390 |
3394 \begin{indentblock} |
3391 \begin{indentblock} |
3395 \begin{description} |
3392 \begin{description} |
3396 |
3393 |
3397 \item[@{text "t."}\hthm{Domainp_rel} @{text "[relator_domain]"}\rm:] ~ \\ |
3394 \item[\<open>t.\<close>\hthm{Domainp_rel} \<open>[relator_domain]\<close>\rm:] ~ \\ |
3398 @{thm list.Domainp_rel[no_vars]} |
3395 @{thm list.Domainp_rel[no_vars]} |
3399 |
3396 |
3400 \item[@{text "t."}\hthm{left_total_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
3397 \item[\<open>t.\<close>\hthm{left_total_rel} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
3401 @{thm list.left_total_rel[no_vars]} |
3398 @{thm list.left_total_rel[no_vars]} |
3402 |
3399 |
3403 \item[@{text "t."}\hthm{left_unique_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
3400 \item[\<open>t.\<close>\hthm{left_unique_rel} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
3404 @{thm list.left_unique_rel[no_vars]} |
3401 @{thm list.left_unique_rel[no_vars]} |
3405 |
3402 |
3406 \item[@{text "t."}\hthm{right_total_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
3403 \item[\<open>t.\<close>\hthm{right_total_rel} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
3407 @{thm list.right_total_rel[no_vars]} |
3404 @{thm list.right_total_rel[no_vars]} |
3408 |
3405 |
3409 \item[@{text "t."}\hthm{right_unique_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
3406 \item[\<open>t.\<close>\hthm{right_unique_rel} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
3410 @{thm list.right_unique_rel[no_vars]} |
3407 @{thm list.right_unique_rel[no_vars]} |
3411 |
3408 |
3412 \item[@{text "t."}\hthm{bi_total_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
3409 \item[\<open>t.\<close>\hthm{bi_total_rel} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
3413 @{thm list.bi_total_rel[no_vars]} |
3410 @{thm list.bi_total_rel[no_vars]} |
3414 |
3411 |
3415 \item[@{text "t."}\hthm{bi_unique_rel} @{text "[transfer_rule]"}\rm:] ~ \\ |
3412 \item[\<open>t.\<close>\hthm{bi_unique_rel} \<open>[transfer_rule]\<close>\rm:] ~ \\ |
3416 @{thm list.bi_unique_rel[no_vars]} |
3413 @{thm list.bi_unique_rel[no_vars]} |
3417 |
3414 |
3418 \end{description} |
3415 \end{description} |
3419 \end{indentblock} |
3416 \end{indentblock} |
3420 |
3417 |
3421 For (co)datatypes with at least one live type argument, the plugin sets the |
3418 For (co)datatypes with at least one live type argument, the plugin sets the |
3422 @{text "[transfer_rule]"} attribute on the following (co)datatypes properties: |
3419 \<open>[transfer_rule]\<close> attribute on the following (co)datatypes properties: |
3423 @{text "t.case_"}\allowbreak @{text "transfer"}, |
3420 \<open>t.case_\<close>\allowbreak \<open>transfer\<close>, |
3424 @{text "t.sel_"}\allowbreak @{text "transfer"}, |
3421 \<open>t.sel_\<close>\allowbreak \<open>transfer\<close>, |
3425 @{text "t.ctr_"}\allowbreak @{text "transfer"}, |
3422 \<open>t.ctr_\<close>\allowbreak \<open>transfer\<close>, |
3426 @{text "t.disc_"}\allowbreak @{text "transfer"}, |
3423 \<open>t.disc_\<close>\allowbreak \<open>transfer\<close>, |
3427 @{text "t.rec_"}\allowbreak @{text "transfer"}, and |
3424 \<open>t.rec_\<close>\allowbreak \<open>transfer\<close>, and |
3428 @{text "t.corec_"}\allowbreak @{text "transfer"}. |
3425 \<open>t.corec_\<close>\allowbreak \<open>transfer\<close>. |
3429 For (co)datatypes that further have \emph{no dead type arguments}, the plugin |
3426 For (co)datatypes that further have \emph{no dead type arguments}, the plugin |
3430 sets @{text "[transfer_rule]"} on |
3427 sets \<open>[transfer_rule]\<close> on |
3431 @{text "t.set_"}\allowbreak @{text "transfer"}, |
3428 \<open>t.set_\<close>\allowbreak \<open>transfer\<close>, |
3432 @{text "t.map_"}\allowbreak @{text "transfer"}, and |
3429 \<open>t.map_\<close>\allowbreak \<open>transfer\<close>, and |
3433 @{text "t.rel_"}\allowbreak @{text "transfer"}. |
3430 \<open>t.rel_\<close>\allowbreak \<open>transfer\<close>. |
3434 |
3431 |
3435 For @{command primrec}, @{command primcorec}, and @{command primcorecursive}, |
3432 For @{command primrec}, @{command primcorec}, and @{command primcorecursive}, |
3436 the plugin implements the generation of the @{text "f.transfer"} property, |
3433 the plugin implements the generation of the \<open>f.transfer\<close> property, |
3437 conditioned by the @{text transfer} option, and sets the |
3434 conditioned by the \<open>transfer\<close> option, and sets the |
3438 @{text "[transfer_rule]"} attribute on these. |
3435 \<open>[transfer_rule]\<close> attribute on these. |
3439 \<close> |
3436 \<close> |
3440 |
3437 |
3441 |
3438 |
3442 subsection \<open>Lifting |
3439 subsection \<open>Lifting |
3443 \label{ssec:lifting}\<close> |
3440 \label{ssec:lifting}\<close> |
3450 The plugin derives the following property: |
3447 The plugin derives the following property: |
3451 |
3448 |
3452 \begin{indentblock} |
3449 \begin{indentblock} |
3453 \begin{description} |
3450 \begin{description} |
3454 |
3451 |
3455 \item[@{text "t."}\hthm{Quotient} @{text "[quot_map]"}\rm:] ~ \\ |
3452 \item[\<open>t.\<close>\hthm{Quotient} \<open>[quot_map]\<close>\rm:] ~ \\ |
3456 @{thm list.Quotient[no_vars]} |
3453 @{thm list.Quotient[no_vars]} |
3457 |
3454 |
3458 \end{description} |
3455 \end{description} |
3459 \end{indentblock} |
3456 \end{indentblock} |
3460 |
3457 |
3461 In addition, the plugin sets the @{text "[relator_eq]"} attribute on a |
3458 In addition, the plugin sets the \<open>[relator_eq]\<close> attribute on a |
3462 variant of the @{text t.rel_eq_onp} property, the @{text "[relator_mono]"} |
3459 variant of the \<open>t.rel_eq_onp\<close> property, the \<open>[relator_mono]\<close> |
3463 attribute on @{text t.rel_mono}, and the @{text "[relator_distr]"} attribute |
3460 attribute on \<open>t.rel_mono\<close>, and the \<open>[relator_distr]\<close> attribute |
3464 on @{text t.rel_compp}. |
3461 on \<open>t.rel_compp\<close>. |
3465 \<close> |
3462 \<close> |
3466 |
3463 |
3467 |
3464 |
3468 subsection \<open>Quickcheck |
3465 subsection \<open>Quickcheck |
3469 \label{ssec:quickcheck}\<close> |
3466 \label{ssec:quickcheck}\<close> |
3520 attributes next to the entered formulas.} The less convenient syntax, using the |
3517 attributes next to the entered formulas.} The less convenient syntax, using the |
3521 \keyw{lemmas} command, is available as an alternative. |
3518 \keyw{lemmas} command, is available as an alternative. |
3522 |
3519 |
3523 \item |
3520 \item |
3524 \emph{The \emph{\keyw{primcorec}} command does not allow corecursion under |
3521 \emph{The \emph{\keyw{primcorec}} command does not allow corecursion under |
3525 @{text "case"}--@{text "of"} for datatypes that are defined without |
3522 \<open>case\<close>--\<open>of\<close> for datatypes that are defined without |
3526 discriminators and selectors.} |
3523 discriminators and selectors.} |
3527 |
3524 |
3528 \item |
3525 \item |
3529 \emph{There is no way to use an overloaded constant from a syntactic type |
3526 \emph{There is no way to use an overloaded constant from a syntactic type |
3530 class, such as @{text 0}, as a constructor.} |
3527 class, such as \<open>0\<close>, as a constructor.} |
3531 |
3528 |
3532 \item |
3529 \item |
3533 \emph{There is no way to register the same type as both a datatype and a |
3530 \emph{There is no way to register the same type as both a datatype and a |
3534 codatatype.} This affects types such as the extended natural numbers, for which |
3531 codatatype.} This affects types such as the extended natural numbers, for which |
3535 both views would make sense (for a different set of constructors). |
3532 both views would make sense (for a different set of constructors). |
3551 |
3548 |
3552 Tobias Nipkow and Makarius Wenzel encouraged us to implement the new |
3549 Tobias Nipkow and Makarius Wenzel encouraged us to implement the new |
3553 (co)datatype package. Andreas Lochbihler provided lots of comments on earlier |
3550 (co)datatype package. Andreas Lochbihler provided lots of comments on earlier |
3554 versions of the package, especially on the coinductive part. Brian Huffman |
3551 versions of the package, especially on the coinductive part. Brian Huffman |
3555 suggested major simplifications to the internal constructions. Ond\v{r}ej |
3552 suggested major simplifications to the internal constructions. Ond\v{r}ej |
3556 Kun\v{c}ar implemented the @{text transfer} and @{text lifting} plugins. |
3553 Kun\v{c}ar implemented the \<open>transfer\<close> and \<open>lifting\<close> plugins. |
3557 Christian Sternagel and Ren\'e Thiemann ported the \keyw{derive} command |
3554 Christian Sternagel and Ren\'e Thiemann ported the \keyw{derive} command |
3558 from the \emph{Archive of Formal Proofs} to the new datatypes. Gerwin Klein and |
3555 from the \emph{Archive of Formal Proofs} to the new datatypes. Gerwin Klein and |
3559 Lars Noschinski implemented the @{command simps_of_case} and @{command |
3556 Lars Noschinski implemented the @{command simps_of_case} and @{command |
3560 case_of_simps} commands. Florian Haftmann, Christian Urban, and Makarius |
3557 case_of_simps} commands. Florian Haftmann, Christian Urban, and Makarius |
3561 Wenzel provided general advice on Isabelle and package writing. Stefan Milius |
3558 Wenzel provided general advice on Isabelle and package writing. Stefan Milius |