src/Doc/Datatypes/Datatypes.thy
changeset 53829 92e71eb22ebe
parent 53828 408c9a3617e3
child 53831 80423b9080cf
equal deleted inserted replaced
53828:408c9a3617e3 53829:92e71eb22ebe
   120 \item Section \ref{sec:defining-recursive-functions}, ``Defining Recursive
   120 \item Section \ref{sec:defining-recursive-functions}, ``Defining Recursive
   121 Functions,'' describes how to specify recursive functions using
   121 Functions,'' describes how to specify recursive functions using
   122 @{command primrec_new}, \keyw{fun}, and \keyw{function}.
   122 @{command primrec_new}, \keyw{fun}, and \keyw{function}.
   123 
   123 
   124 \item Section \ref{sec:defining-codatatypes}, ``Defining Codatatypes,''
   124 \item Section \ref{sec:defining-codatatypes}, ``Defining Codatatypes,''
   125 describes how to specify codatatypes using the \keyw{codatatype} command.
   125 describes how to specify codatatypes using the @{command codatatype} command.
   126 
   126 
   127 \item Section \ref{sec:defining-corecursive-functions}, ``Defining Corecursive
   127 \item Section \ref{sec:defining-corecursive-functions}, ``Defining Corecursive
   128 Functions,'' describes how to specify corecursive functions using the
   128 Functions,'' describes how to specify corecursive functions using the
   129 @{command primcorec} and @{command primcorecursive} commands.
   129 @{command primcorec} and @{command primcorecursive} commands.
   130 
   130 
   135 \item Section
   135 \item Section
   136 \ref{sec:deriving-destructors-and-theorems-for-free-constructors},
   136 \ref{sec:deriving-destructors-and-theorems-for-free-constructors},
   137 ``Deriving Destructors and Theorems for Free Constructors,'' explains how to
   137 ``Deriving Destructors and Theorems for Free Constructors,'' explains how to
   138 use the command @{command wrap_free_constructors} to derive destructor constants
   138 use the command @{command wrap_free_constructors} to derive destructor constants
   139 and theorems for freely generated types, as performed internally by @{command
   139 and theorems for freely generated types, as performed internally by @{command
   140 datatype_new} and \keyw{codatatype}.
   140 datatype_new} and @{command codatatype}.
   141 
   141 
   142 %\item Section \ref{sec:standard-ml-interface}, ``Standard ML Interface,''
   142 %\item Section \ref{sec:standard-ml-interface}, ``Standard ML Interface,''
   143 %describes the package's programmatic interface.
   143 %describes the package's programmatic interface.
   144 
   144 
   145 %\item Section \ref{sec:interoperability}, ``Interoperability,''
   145 %\item Section \ref{sec:interoperability}, ``Interoperability,''
   339 type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and
   339 type arguments are called \emph{dead}. In @{typ "'a \<Rightarrow> 'b"} and
   340 @{typ "('a, 'b) fn"}, the type variable @{typ 'a} is dead and @{typ 'b} is live.
   340 @{typ "('a, 'b) fn"}, the type variable @{typ 'a} is dead and @{typ 'b} is live.
   341 
   341 
   342 Type constructors must be registered as BNFs to have live arguments. This is
   342 Type constructors must be registered as BNFs to have live arguments. This is
   343 done automatically for datatypes and codatatypes introduced by the @{command
   343 done automatically for datatypes and codatatypes introduced by the @{command
   344 datatype_new} and \keyw{codatatype} commands.
   344 datatype_new} and @{command codatatype} commands.
   345 Section~\ref{sec:registering-bounded-natural-functors} explains how to register
   345 Section~\ref{sec:registering-bounded-natural-functors} explains how to register
   346 arbitrary type constructors as BNFs.
   346 arbitrary type constructors as BNFs.
   347 *}
   347 *}
   348 
   348 
   349 
   349 
   437 
   437 
   438 subsubsection {* \keyw{datatype\_new}
   438 subsubsection {* \keyw{datatype\_new}
   439   \label{sssec:datatype-new} *}
   439   \label{sssec:datatype-new} *}
   440 
   440 
   441 text {*
   441 text {*
   442 Datatype definitions have the following general syntax:
   442 \begin{matharray}{rcl}
       
   443   @{command_def "datatype_new"} & : & @{text "local_theory \<rightarrow> local_theory"}
       
   444 \end{matharray}
   443 
   445 
   444 @{rail "
   446 @{rail "
   445   @@{command_def datatype_new} target? @{syntax dt_options}? \\
   447   @@{command datatype_new} target? @{syntax dt_options}? \\
   446     (@{syntax dt_name} '=' (@{syntax ctor} + '|') + @'and')
   448     (@{syntax dt_name} '=' (@{syntax ctor} + '|') + @'and')
   447   ;
   449   ;
   448   @{syntax_def dt_options}: '(' (('no_discs_sels' | 'rep_compat') + ',') ')'
   450   @{syntax_def dt_options}: '(' (('no_discs_sels' | 'rep_compat') + ',') ')'
   449 "}
   451 "}
   450 
   452 
   532 
   534 
   533 subsubsection {* \keyw{datatype\_new\_compat}
   535 subsubsection {* \keyw{datatype\_new\_compat}
   534   \label{sssec:datatype-new-compat} *}
   536   \label{sssec:datatype-new-compat} *}
   535 
   537 
   536 text {*
   538 text {*
       
   539 \begin{matharray}{rcl}
       
   540   @{command_def "datatype_new_compat"} & : & @{text "local_theory \<rightarrow> local_theory"}
       
   541 \end{matharray}
       
   542 
       
   543 @{rail "
       
   544   @@{command datatype_new_compat} names
       
   545 "}
       
   546 
       
   547 \noindent
   537 The old datatype package provides some functionality that is not yet replicated
   548 The old datatype package provides some functionality that is not yet replicated
   538 in the new package:
   549 in the new package:
   539 
   550 
   540 \begin{itemize}
   551 \begin{itemize}
   541 \setlength{\itemsep}{0pt}
   552 \setlength{\itemsep}{0pt}
   548 @{const size} function.
   559 @{const size} function.
   549 \end{itemize}
   560 \end{itemize}
   550 
   561 
   551 \noindent
   562 \noindent
   552 New-style datatypes can in most case be registered as old-style datatypes using
   563 New-style datatypes can in most case be registered as old-style datatypes using
   553 the command
   564 @{command datatype_new_compat}. The \textit{names} argument is a space-separated
   554 
   565 list of type names that are mutually recursive. For example:
   555 @{rail "
       
   556   @@{command_def datatype_new_compat} names
       
   557 "}
       
   558 
       
   559 \noindent
       
   560 where the \textit{names} argument is simply a space-separated list of type names
       
   561 that are mutually recursive. For example:
       
   562 *}
   566 *}
   563 
   567 
   564     datatype_new_compat even_nat odd_nat
   568     datatype_new_compat even_nat odd_nat
   565 
   569 
   566 text {* \blankline *}
   570 text {* \blankline *}
  1209 
  1213 
  1210 subsubsection {* \keyw{primrec\_new}
  1214 subsubsection {* \keyw{primrec\_new}
  1211   \label{sssec:primrec-new} *}
  1215   \label{sssec:primrec-new} *}
  1212 
  1216 
  1213 text {*
  1217 text {*
  1214 Primitive recursive functions have the following general syntax:
  1218 \begin{matharray}{rcl}
       
  1219   @{command_def "primrec_new"} & : & @{text "local_theory \<rightarrow> local_theory"}
       
  1220 \end{matharray}
  1215 
  1221 
  1216 @{rail "
  1222 @{rail "
  1217   @@{command_def primrec_new} target? fixes \\ @'where'
  1223   @@{command primrec_new} target? fixes \\ @'where' (@{syntax pr_equation} + '|')
  1218     (@{syntax primrec_equation} + '|')
       
  1219   ;
  1224   ;
  1220   @{syntax_def primrec_equation}: thmdecl? prop
  1225   @{syntax_def pr_equation}: thmdecl? prop
  1221 "}
  1226 "}
  1222 *}
  1227 *}
  1223 
  1228 
  1224 
  1229 
  1225 (*
  1230 (*
  1320 
  1325 
  1321 section {* Defining Codatatypes
  1326 section {* Defining Codatatypes
  1322   \label{sec:defining-codatatypes} *}
  1327   \label{sec:defining-codatatypes} *}
  1323 
  1328 
  1324 text {*
  1329 text {*
  1325 Codatatypes can be specified using the \keyw{codatatype} command. The
  1330 Codatatypes can be specified using the @{command codatatype} command. The
  1326 command is first illustrated through concrete examples featuring different
  1331 command is first illustrated through concrete examples featuring different
  1327 flavors of corecursion. More examples can be found in the directory
  1332 flavors of corecursion. More examples can be found in the directory
  1328 \verb|~~/src/HOL/BNF/Examples|. The \emph{Archive of Formal Proofs} also
  1333 \verb|~~/src/HOL/BNF/Examples|. The \emph{Archive of Formal Proofs} also
  1329 includes some useful codatatypes, notably for lazy lists \cite{lochbihler-2010}.
  1334 includes some useful codatatypes, notably for lazy lists \cite{lochbihler-2010}.
  1330 *}
  1335 *}
  1380     | Skip (cont: "'a process")
  1385     | Skip (cont: "'a process")
  1381     | Action (prefix: 'a) (cont: "'a process")
  1386     | Action (prefix: 'a) (cont: "'a process")
  1382     | Choice (left: "'a process") (right: "'a process")
  1387     | Choice (left: "'a process") (right: "'a process")
  1383 
  1388 
  1384 text {*
  1389 text {*
       
  1390 \noindent
  1385 Notice that the @{const cont} selector is associated with both @{const Skip}
  1391 Notice that the @{const cont} selector is associated with both @{const Skip}
  1386 and @{const Choice}.
  1392 and @{const Choice}.
  1387 *}
  1393 *}
  1388 
  1394 
  1389 
  1395 
  1425 
  1431 
  1426 subsubsection {* \keyw{codatatype}
  1432 subsubsection {* \keyw{codatatype}
  1427   \label{sssec:codatatype} *}
  1433   \label{sssec:codatatype} *}
  1428 
  1434 
  1429 text {*
  1435 text {*
       
  1436 \begin{matharray}{rcl}
       
  1437   @{command_def "codatatype"} & : & @{text "local_theory \<rightarrow> local_theory"}
       
  1438 \end{matharray}
       
  1439 
       
  1440 @{rail "
       
  1441   @@{command codatatype} target? \\
       
  1442     (@{syntax dt_name} '=' (@{syntax ctor} + '|') + @'and')
       
  1443 "}
       
  1444 
       
  1445 \noindent
  1430 Definitions of codatatypes have almost exactly the same syntax as for datatypes
  1446 Definitions of codatatypes have almost exactly the same syntax as for datatypes
  1431 (Section~\ref{ssec:datatype-command-syntax}), with two exceptions: The command
  1447 (Section~\ref{ssec:datatype-command-syntax}). The @{text "no_discs_sels"} option
  1432 is called \keyw{codatatype}. The @{text "no_discs_sels"} option is not
  1448 is not available, because destructors are a crucial notion for codatatypes.
  1433 available, because destructors are a crucial notion for codatatypes.
       
  1434 *}
  1449 *}
  1435 
  1450 
  1436 
  1451 
  1437 subsection {* Generated Constants
  1452 subsection {* Generated Constants
  1438   \label{ssec:codatatype-generated-constants} *}
  1453   \label{ssec:codatatype-generated-constants} *}
  1457 
  1472 
  1458 subsection {* Generated Theorems
  1473 subsection {* Generated Theorems
  1459   \label{ssec:codatatype-generated-theorems} *}
  1474   \label{ssec:codatatype-generated-theorems} *}
  1460 
  1475 
  1461 text {*
  1476 text {*
  1462 The characteristic theorems generated by \keyw{codatatype} are grouped in
  1477 The characteristic theorems generated by @{command codatatype} are grouped in
  1463 three broad categories:
  1478 three broad categories:
  1464 
  1479 
  1465 \begin{itemize}
  1480 \begin{itemize}
  1466 \setlength{\itemsep}{0pt}
  1481 \setlength{\itemsep}{0pt}
  1467 
  1482 
  1545 
  1560 
  1546 \end{description}
  1561 \end{description}
  1547 \end{indentblock}
  1562 \end{indentblock}
  1548 
  1563 
  1549 \noindent
  1564 \noindent
  1550 For convenience, \keyw{codatatype} also provides the following collection:
  1565 For convenience, @{command codatatype} also provides the following collection:
  1551 
  1566 
  1552 \begin{indentblock}
  1567 \begin{indentblock}
  1553 \begin{description}
  1568 \begin{description}
  1554 
  1569 
  1555 \item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.corec}$^*$ @{text t.disc_corec}] ~ \\
  1570 \item[@{text "t."}\hthm{simps} = @{text t.inject} @{text t.distinct} @{text t.case} @{text t.corec}$^*$ @{text t.disc_corec}] ~ \\
  2018 
  2033 
  2019 subsubsection {* \keyw{primcorec} and \keyw{primcorecursive}
  2034 subsubsection {* \keyw{primcorec} and \keyw{primcorecursive}
  2020   \label{sssec:primcorecursive-and-primcorec} *}
  2035   \label{sssec:primcorecursive-and-primcorec} *}
  2021 
  2036 
  2022 text {*
  2037 text {*
  2023 Primitive corecursive definitions have the following general syntax:
  2038 \begin{matharray}{rcl}
       
  2039   @{command_def "primcorec"} & : & @{text "local_theory \<rightarrow> local_theory"} \\
       
  2040   @{command_def "primcorecursive"} & : & @{text "local_theory \<rightarrow> proof(prove)"}
       
  2041 \end{matharray}
  2024 
  2042 
  2025 @{rail "
  2043 @{rail "
  2026   (@@{command_def primcorec} | @@{command_def primcorecursive}) target? \\ @{syntax pcr_option}? fixes @'where'
  2044   (@@{command primcorec} | @@{command primcorecursive}) target? \\ @{syntax pcr_option}? fixes @'where'
  2027     (@{syntax pcr_formula} + '|')
  2045     (@{syntax pcr_formula} + '|')
  2028   ;
  2046   ;
  2029   @{syntax_def pcr_option}: '(' ('sequential' | 'exhaustive') ')'
  2047   @{syntax_def pcr_option}: '(' ('sequential' | 'exhaustive') ')'
  2030   ;
  2048   ;
  2031   @{syntax_def pcr_formula}: thmdecl? prop (@'of' (term * ))?
  2049   @{syntax_def pcr_formula}: thmdecl? prop (@'of' (term * ))?
  2099 
  2117 
  2100 subsubsection {* \keyw{bnf}
  2118 subsubsection {* \keyw{bnf}
  2101   \label{sssec:bnf} *}
  2119   \label{sssec:bnf} *}
  2102 
  2120 
  2103 text {*
  2121 text {*
       
  2122 \begin{matharray}{rcl}
       
  2123   @{command_def "bnf"} & : & @{text "local_theory \<rightarrow> proof(prove)"}
       
  2124 \end{matharray}
       
  2125 
  2104 @{rail "
  2126 @{rail "
  2105   @@{command_def bnf} target? (name ':')? term \\
  2127   @@{command bnf} target? (name ':')? term \\
  2106     term_list term term_list term?
  2128     term_list term term_list term?
  2107   ;
  2129   ;
  2108   X_list: '[' (X + ',') ']'
  2130   X_list: '[' (X + ',') ']'
  2109 "}
  2131 "}
  2110 *}
  2132 *}
  2112 
  2134 
  2113 subsubsection {* \keyw{print\_bnfs}
  2135 subsubsection {* \keyw{print\_bnfs}
  2114   \label{sssec:print-bnfs} *}
  2136   \label{sssec:print-bnfs} *}
  2115 
  2137 
  2116 text {*
  2138 text {*
       
  2139 \begin{matharray}{rcl}
       
  2140   @{command_def "print_bnfs"} & : & @{text "local_theory \<rightarrow>"}
       
  2141 \end{matharray}
       
  2142 
  2117 @{rail "
  2143 @{rail "
  2118   @@{command_def print_bnfs}
  2144   @@{command print_bnfs}
  2119 "}
  2145 "}
  2120 *}
  2146 *}
  2121 
  2147 
  2122 
  2148 
  2123 section {* Deriving Destructors and Theorems for Free Constructors
  2149 section {* Deriving Destructors and Theorems for Free Constructors
  2124   \label{sec:deriving-destructors-and-theorems-for-free-constructors} *}
  2150   \label{sec:deriving-destructors-and-theorems-for-free-constructors} *}
  2125 
  2151 
  2126 text {*
  2152 text {*
  2127 The derivation of convenience theorems for types equipped with free constructors,
  2153 The derivation of convenience theorems for types equipped with free constructors,
  2128 as performed internally by @{command datatype_new} and \keyw{codatatype},
  2154 as performed internally by @{command datatype_new} and @{command codatatype},
  2129 is available as a stand-alone command called @{command wrap_free_constructors}.
  2155 is available as a stand-alone command called @{command wrap_free_constructors}.
  2130 
  2156 
  2131 %  * need for this is rare but may arise if you want e.g. to add destructors to
  2157 %  * need for this is rare but may arise if you want e.g. to add destructors to
  2132 %    a type not introduced by ...
  2158 %    a type not introduced by ...
  2133 %
  2159 %
  2152 
  2178 
  2153 subsubsection {* \keyw{wrap\_free\_constructors}
  2179 subsubsection {* \keyw{wrap\_free\_constructors}
  2154   \label{sssec:wrap-free-constructors} *}
  2180   \label{sssec:wrap-free-constructors} *}
  2155 
  2181 
  2156 text {*
  2182 text {*
  2157 Free constructor wrapping has the following general syntax:
  2183 \begin{matharray}{rcl}
       
  2184   @{command_def "wrap_free_constructors"} & : & @{text "local_theory \<rightarrow> proof(prove)"}
       
  2185 \end{matharray}
  2158 
  2186 
  2159 @{rail "
  2187 @{rail "
  2160   @@{command_def wrap_free_constructors} target? @{syntax dt_options} \\
  2188   @@{command wrap_free_constructors} target? @{syntax dt_options} \\
  2161     term_list name @{syntax fc_discs_sels}?
  2189     term_list name @{syntax fc_discs_sels}?
  2162   ;
  2190   ;
  2163   @{syntax_def fc_discs_sels}: name_list (name_list_list name_term_list_list? )?
  2191   @{syntax_def fc_discs_sels}: name_list (name_list_list name_term_list_list? )?
  2164   ;
  2192   ;
  2165   @{syntax_def name_term}: (name ':' term)
  2193   @{syntax_def name_term}: (name ':' term)
  2167 
  2195 
  2168 % options: no_discs_sels rep_compat
  2196 % options: no_discs_sels rep_compat
  2169 
  2197 
  2170 % X_list is as for BNF
  2198 % X_list is as for BNF
  2171 
  2199 
       
  2200 \noindent
  2172 Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems.
  2201 Section~\ref{ssec:datatype-generated-theorems} lists the generated theorems.
  2173 *}
  2202 *}
  2174 
  2203 
  2175 
  2204 
  2176 (*
  2205 (*