76 allow infinite paths. Orthogonally, the nodes in the first and third types have |
76 allow infinite paths. Orthogonally, the nodes in the first and third types have |
77 finitely many direct subtrees, whereas those of the second and fourth may have |
77 finitely many direct subtrees, whereas those of the second and fourth may have |
78 infinite branching. |
78 infinite branching. |
79 |
79 |
80 The package is part of @{theory Main}. Additional functionality is provided by |
80 The package is part of @{theory Main}. Additional functionality is provided by |
81 the theory @{file "~~/src/HOL/Library/BNF_Axiomatization.thy"}. |
81 the theory \<^file>\<open>~~/src/HOL/Library/BNF_Axiomatization.thy\<close>. |
82 |
82 |
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 |
161 \label{ssec:datatype-introductory-examples}\<close> |
161 \label{ssec:datatype-introductory-examples}\<close> |
162 |
162 |
163 text \<open> |
163 text \<open> |
164 Datatypes are illustrated through concrete examples featuring different flavors |
164 Datatypes are illustrated through concrete examples featuring different flavors |
165 of recursion. More examples can be found in the directory |
165 of recursion. More examples can be found in the directory |
166 @{dir "~~/src/HOL/Datatype_Examples"}. |
166 \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>. |
167 \<close> |
167 \<close> |
168 |
168 |
169 |
169 |
170 subsubsection \<open>Nonrecursive Types |
170 subsubsection \<open>Nonrecursive Types |
171 \label{sssec:datatype-nonrecursive-types}\<close> |
171 \label{sssec:datatype-nonrecursive-types}\<close> |
1136 |
1136 |
1137 subsubsection \<open>\textit{countable_datatype} |
1137 subsubsection \<open>\textit{countable_datatype} |
1138 \label{sssec:datatype-compat}\<close> |
1138 \label{sssec:datatype-compat}\<close> |
1139 |
1139 |
1140 text \<open> |
1140 text \<open> |
1141 The theory @{file "~~/src/HOL/Library/Countable.thy"} provides a |
1141 The theory \<^file>\<open>~~/src/HOL/Library/Countable.thy\<close> provides a |
1142 proof method called @{method countable_datatype} that can be used to prove the |
1142 proof method called @{method countable_datatype} that can be used to prove the |
1143 countability of many datatypes, building on the countability of the types |
1143 countability of many datatypes, building on the countability of the types |
1144 appearing in their definitions and of any type arguments. For example: |
1144 appearing in their definitions and of any type arguments. For example: |
1145 \<close> |
1145 \<close> |
1146 |
1146 |
1216 @{text "[where \<dots>]"} attribute. The solution is to use the more robust |
1216 @{text "[where \<dots>]"} attribute. The solution is to use the more robust |
1217 @{text "[of \<dots>]"} syntax. |
1217 @{text "[of \<dots>]"} syntax. |
1218 \end{itemize} |
1218 \end{itemize} |
1219 |
1219 |
1220 The old command is still available as \keyw{old_datatype} in theory |
1220 The old command is still available as \keyw{old_datatype} in theory |
1221 @{file "~~/src/HOL/Library/Old_Datatype.thy"}. However, there is no general |
1221 \<^file>\<open>~~/src/HOL/Library/Old_Datatype.thy\<close>. However, there is no general |
1222 way to register old-style datatypes as new-style datatypes. If the objective |
1222 way to register old-style datatypes as new-style datatypes. If the objective |
1223 is to define new-style datatypes with nested recursion through old-style |
1223 is to define new-style datatypes with nested recursion through old-style |
1224 datatypes, the old-style datatypes can be registered as a BNF |
1224 datatypes, the old-style datatypes can be registered as a BNF |
1225 (Section~\ref{sec:registering-bounded-natural-functors}). If the objective is |
1225 (Section~\ref{sec:registering-bounded-natural-functors}). If the objective is |
1226 to derive discriminators and selectors, this can be achieved using |
1226 to derive discriminators and selectors, this can be achieved using |
1245 \label{ssec:primrec-introductory-examples}\<close> |
1245 \label{ssec:primrec-introductory-examples}\<close> |
1246 |
1246 |
1247 text \<open> |
1247 text \<open> |
1248 Primitive recursion is illustrated through concrete examples based on the |
1248 Primitive recursion is illustrated through concrete examples based on the |
1249 datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More |
1249 datatypes defined in Section~\ref{ssec:datatype-introductory-examples}. More |
1250 examples can be found in the directory @{dir "~~/src/HOL/Datatype_Examples"}. |
1250 examples can be found in the directory \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>. |
1251 \<close> |
1251 \<close> |
1252 |
1252 |
1253 |
1253 |
1254 subsubsection \<open>Nonrecursive Types |
1254 subsubsection \<open>Nonrecursive Types |
1255 \label{sssec:primrec-nonrecursive-types}\<close> |
1255 \label{sssec:primrec-nonrecursive-types}\<close> |
1318 text \<open> |
1318 text \<open> |
1319 \noindent |
1319 \noindent |
1320 Pattern matching is only available for the argument on which the recursion takes |
1320 Pattern matching is only available for the argument on which the recursion takes |
1321 place. Fortunately, it is easy to generate pattern-maching equations using the |
1321 place. Fortunately, it is easy to generate pattern-maching equations using the |
1322 @{command simps_of_case} command provided by the theory |
1322 @{command simps_of_case} command provided by the theory |
1323 @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"}. |
1323 \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close>. |
1324 \<close> |
1324 \<close> |
1325 |
1325 |
1326 simps_of_case at_simps_alt: at.simps |
1326 simps_of_case at_simps_alt: at.simps |
1327 |
1327 |
1328 text \<open> |
1328 text \<open> |
1758 |
1758 |
1759 text \<open> |
1759 text \<open> |
1760 Codatatypes can be specified using the @{command codatatype} command. The |
1760 Codatatypes can be specified using the @{command codatatype} command. The |
1761 command is first illustrated through concrete examples featuring different |
1761 command is first illustrated through concrete examples featuring different |
1762 flavors of corecursion. More examples can be found in the directory |
1762 flavors of corecursion. More examples can be found in the directory |
1763 @{dir "~~/src/HOL/Datatype_Examples"}. The \emph{Archive of Formal Proofs} also |
1763 \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>. The \emph{Archive of Formal Proofs} also |
1764 includes some useful codatatypes, notably for lazy lists @{cite |
1764 includes some useful codatatypes, notably for lazy lists @{cite |
1765 "lochbihler-2010"}. |
1765 "lochbihler-2010"}. |
1766 \<close> |
1766 \<close> |
1767 |
1767 |
1768 |
1768 |
2036 \keyw{corec} and \keyw{corecursive} commands, and techniques based on domains |
2036 \keyw{corec} and \keyw{corecursive} commands, and techniques based on domains |
2037 and topologies @{cite "lochbihler-hoelzl-2014"}. In this tutorial, the focus is |
2037 and topologies @{cite "lochbihler-hoelzl-2014"}. In this tutorial, the focus is |
2038 on @{command primcorec} and @{command primcorecursive}; \keyw{corec} and |
2038 on @{command primcorec} and @{command primcorecursive}; \keyw{corec} and |
2039 \keyw{corecursive} are described in a separate tutorial |
2039 \keyw{corecursive} are described in a separate tutorial |
2040 @{cite "isabelle-corec"}. More examples can be found in the directories |
2040 @{cite "isabelle-corec"}. More examples can be found in the directories |
2041 @{dir "~~/src/HOL/Datatype_Examples"} and @{dir "~~/src/HOL/Corec_Examples"}. |
2041 \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close> and \<^dir>\<open>~~/src/HOL/Corec_Examples\<close>. |
2042 |
2042 |
2043 Whereas recursive functions consume datatypes one constructor at a time, |
2043 Whereas recursive functions consume datatypes one constructor at a time, |
2044 corecursive functions construct codatatypes one constructor at a time. |
2044 corecursive functions construct codatatypes one constructor at a time. |
2045 Partly reflecting a lack of agreement among proponents of coalgebraic methods, |
2045 Partly reflecting a lack of agreement among proponents of coalgebraic methods, |
2046 Isabelle supports three competing syntaxes for specifying a function $f$: |
2046 Isabelle supports three competing syntaxes for specifying a function $f$: |
2080 \label{ssec:primcorec-introductory-examples}\<close> |
2080 \label{ssec:primcorec-introductory-examples}\<close> |
2081 |
2081 |
2082 text \<open> |
2082 text \<open> |
2083 Primitive corecursion is illustrated through concrete examples based on the |
2083 Primitive corecursion is illustrated through concrete examples based on the |
2084 codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More |
2084 codatatypes defined in Section~\ref{ssec:codatatype-introductory-examples}. More |
2085 examples can be found in the directory @{dir "~~/src/HOL/Datatype_Examples"}. |
2085 examples can be found in the directory \<^dir>\<open>~~/src/HOL/Datatype_Examples\<close>. |
2086 The code view is favored in the examples below. Sections |
2086 The code view is favored in the examples below. Sections |
2087 \ref{ssec:primrec-constructor-view} and \ref{ssec:primrec-destructor-view} |
2087 \ref{ssec:primrec-constructor-view} and \ref{ssec:primrec-destructor-view} |
2088 present the same examples expressed using the constructor and destructor views. |
2088 present the same examples expressed using the constructor and destructor views. |
2089 \<close> |
2089 \<close> |
2090 |
2090 |
2141 For technical reasons, @{text "case"}--@{text "of"} is only supported for |
2141 For technical reasons, @{text "case"}--@{text "of"} is only supported for |
2142 case distinctions on (co)datatypes that provide discriminators and selectors. |
2142 case distinctions on (co)datatypes that provide discriminators and selectors. |
2143 |
2143 |
2144 Pattern matching is not supported by @{command primcorec}. Fortunately, it is |
2144 Pattern matching is not supported by @{command primcorec}. Fortunately, it is |
2145 easy to generate pattern-maching equations using the @{command simps_of_case} |
2145 easy to generate pattern-maching equations using the @{command simps_of_case} |
2146 command provided by the theory @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"}. |
2146 command provided by the theory \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close>. |
2147 \<close> |
2147 \<close> |
2148 |
2148 |
2149 simps_of_case lapp_simps: lapp.code |
2149 simps_of_case lapp_simps: lapp.code |
2150 |
2150 |
2151 text \<open> |
2151 text \<open> |
2774 \label{ssec:bnf-introductory-examples}\<close> |
2774 \label{ssec:bnf-introductory-examples}\<close> |
2775 |
2775 |
2776 text \<open> |
2776 text \<open> |
2777 The example below shows how to register a type as a BNF using the @{command bnf} |
2777 The example below shows how to register a type as a BNF using the @{command bnf} |
2778 command. Some of the proof obligations are best viewed with the theory |
2778 command. Some of the proof obligations are best viewed with the theory |
2779 @{file "~~/src/HOL/Library/Cardinal_Notations.thy"} imported. |
2779 \<^file>\<open>~~/src/HOL/Library/Cardinal_Notations.thy\<close> imported. |
2780 |
2780 |
2781 The type is simply a copy of the function space @{typ "'d \<Rightarrow> 'a"}, where @{typ 'a} |
2781 The type is simply a copy of the function space @{typ "'d \<Rightarrow> 'a"}, where @{typ 'a} |
2782 is live and @{typ 'd} is dead. We introduce it together with its map function, |
2782 is live and @{typ 'd} is dead. We introduce it together with its map function, |
2783 set function, predicator, and relator. |
2783 set function, predicator, and relator. |
2784 \<close> |
2784 \<close> |
2873 Using \keyw{print_theorems} and @{command print_bnfs}, we can contemplate and |
2873 Using \keyw{print_theorems} and @{command print_bnfs}, we can contemplate and |
2874 show the world what we have achieved. |
2874 show the world what we have achieved. |
2875 |
2875 |
2876 This particular example does not need any nonemptiness witness, because the |
2876 This particular example does not need any nonemptiness witness, because the |
2877 one generated by default is good enough, but in general this would be |
2877 one generated by default is good enough, but in general this would be |
2878 necessary. See @{file "~~/src/HOL/Basic_BNFs.thy"}, |
2878 necessary. See \<^file>\<open>~~/src/HOL/Basic_BNFs.thy\<close>, |
2879 @{file "~~/src/HOL/Library/Countable_Set_Type.thy"}, |
2879 \<^file>\<open>~~/src/HOL/Library/Countable_Set_Type.thy\<close>, |
2880 @{file "~~/src/HOL/Library/FSet.thy"}, and |
2880 \<^file>\<open>~~/src/HOL/Library/FSet.thy\<close>, and |
2881 @{file "~~/src/HOL/Library/Multiset.thy"} for further examples of BNF |
2881 \<^file>\<open>~~/src/HOL/Library/Multiset.thy\<close> for further examples of BNF |
2882 registration, some of which feature custom witnesses. |
2882 registration, some of which feature custom witnesses. |
2883 |
2883 |
2884 For many typedefs, lifting the BNF structure from the raw type to the abstract |
2884 For many typedefs, lifting the BNF structure from the raw type to the abstract |
2885 type can be done uniformly. This is the task of the @{command lift_bnf} command. |
2885 type can be done uniformly. This is the task of the @{command lift_bnf} command. |
2886 Using @{command lift_bnf}, the above registration of @{typ "('d, 'a) fn"} as a |
2886 Using @{command lift_bnf}, the above registration of @{typ "('d, 'a) fn"} as a |
3105 is identical to the left-hand side of a @{command datatype} or |
3105 is identical to the left-hand side of a @{command datatype} or |
3106 @{command codatatype} definition. |
3106 @{command codatatype} definition. |
3107 |
3107 |
3108 The command is useful to reason abstractly about BNFs. The axioms are safe |
3108 The command is useful to reason abstractly about BNFs. The axioms are safe |
3109 because there exist BNFs of arbitrary large arities. Applications must import |
3109 because there exist BNFs of arbitrary large arities. Applications must import |
3110 the @{file "~~/src/HOL/Library/BNF_Axiomatization.thy"} theory |
3110 the \<^file>\<open>~~/src/HOL/Library/BNF_Axiomatization.thy\<close> theory |
3111 to use this functionality. |
3111 to use this functionality. |
3112 \<close> |
3112 \<close> |
3113 |
3113 |
3114 |
3114 |
3115 subsubsection \<open>\keyw{print_bnfs} |
3115 subsubsection \<open>\keyw{print_bnfs} |
3208 |
3208 |
3209 \medskip |
3209 \medskip |
3210 |
3210 |
3211 \noindent |
3211 \noindent |
3212 The @{command simps_of_case} command provided by theory |
3212 The @{command simps_of_case} command provided by theory |
3213 @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"} converts a single equation with |
3213 \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close> converts a single equation with |
3214 a complex case expression on the right-hand side into a set of pattern-matching |
3214 a complex case expression on the right-hand side into a set of pattern-matching |
3215 equations. For example, |
3215 equations. For example, |
3216 \<close> |
3216 \<close> |
3217 |
3217 |
3218 (*<*) |
3218 (*<*) |
3247 |
3247 |
3248 \medskip |
3248 \medskip |
3249 |
3249 |
3250 \noindent |
3250 \noindent |
3251 The \keyw{case_of_simps} command provided by theory |
3251 The \keyw{case_of_simps} command provided by theory |
3252 @{file "~~/src/HOL/Library/Simps_Case_Conv.thy"} converts a set of |
3252 \<^file>\<open>~~/src/HOL/Library/Simps_Case_Conv.thy\<close> converts a set of |
3253 pattern-matching equations into single equation with a complex case expression |
3253 pattern-matching equations into single equation with a complex case expression |
3254 on the right-hand side (cf.\ @{command simps_of_case}). For example, |
3254 on the right-hand side (cf.\ @{command simps_of_case}). For example, |
3255 \<close> |
3255 \<close> |
3256 |
3256 |
3257 case_of_simps lapp_case: lapp_simps |
3257 case_of_simps lapp_case: lapp_simps |
3384 @{text "'a\<^sub>1, \<dots>, 'a\<^sub>m"}, by default @{text u} values are given a size of 0. This |
3384 @{text "'a\<^sub>1, \<dots>, 'a\<^sub>m"}, by default @{text u} values are given a size of 0. This |
3385 can be improved upon by registering a custom size function of type |
3385 can be improved upon by registering a custom size function of type |
3386 @{text "('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat"} using |
3386 @{text "('a\<^sub>1 \<Rightarrow> nat) \<Rightarrow> \<dots> \<Rightarrow> ('a\<^sub>m \<Rightarrow> nat) \<Rightarrow> u \<Rightarrow> nat"} using |
3387 the ML function @{ML BNF_LFP_Size.register_size} or |
3387 the ML function @{ML BNF_LFP_Size.register_size} or |
3388 @{ML BNF_LFP_Size.register_size_global}. See theory |
3388 @{ML BNF_LFP_Size.register_size_global}. See theory |
3389 @{file "~~/src/HOL/Library/Multiset.thy"} for an example. |
3389 \<^file>\<open>~~/src/HOL/Library/Multiset.thy\<close> for an example. |
3390 \<close> |
3390 \<close> |
3391 |
3391 |
3392 |
3392 |
3393 subsection \<open>Transfer |
3393 subsection \<open>Transfer |
3394 \label{ssec:transfer}\<close> |
3394 \label{ssec:transfer}\<close> |