src/Doc/Datatypes/Datatypes.thy
changeset 69505 cc2d676d5395
parent 68484 59793df7f853
child 69597 ff784d5a5bfb
equal deleted inserted replaced
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