src/Doc/Codegen/Foundations.thy
changeset 69505 cc2d676d5395
parent 68484 59793df7f853
child 69597 ff784d5a5bfb
equal deleted inserted replaced
69504:bda7527ccf05 69505:cc2d676d5395
    54     \label{fig:arch}
    54     \label{fig:arch}
    55   \end{figure}
    55   \end{figure}
    56 
    56 
    57   \noindent Central to code generation is the notion of \emph{code
    57   \noindent Central to code generation is the notion of \emph{code
    58   equations}.  A code equation as a first approximation is a theorem
    58   equations}.  A code equation as a first approximation is a theorem
    59   of the form @{text "f t\<^sub>1 t\<^sub>2 \<dots> t\<^sub>n \<equiv> t"} (an equation headed by a
    59   of the form \<open>f t\<^sub>1 t\<^sub>2 \<dots> t\<^sub>n \<equiv> t\<close> (an equation headed by a
    60   constant @{text f} with arguments @{text "t\<^sub>1 t\<^sub>2 \<dots> t\<^sub>n"} and right
    60   constant \<open>f\<close> with arguments \<open>t\<^sub>1 t\<^sub>2 \<dots> t\<^sub>n\<close> and right
    61   hand side @{text t}).
    61   hand side \<open>t\<close>).
    62 
    62 
    63   \begin{itemize}
    63   \begin{itemize}
    64 
    64 
    65     \item Starting point of code generation is a collection of (raw)
    65     \item Starting point of code generation is a collection of (raw)
    66       code equations in a theory. It is not relevant where they stem
    66       code equations in a theory. It is not relevant where they stem
    73       ML-based theorem transformations to code generation.  The result
    73       ML-based theorem transformations to code generation.  The result
    74       of preprocessing is a structured collection of code equations.
    74       of preprocessing is a structured collection of code equations.
    75 
    75 
    76     \item These code equations are \qn{translated} to a program in an
    76     \item These code equations are \qn{translated} to a program in an
    77       abstract intermediate language.  Think of it as a kind of
    77       abstract intermediate language.  Think of it as a kind of
    78       \qt{Mini-Haskell} with four \qn{statements}: @{text data} (for
    78       \qt{Mini-Haskell} with four \qn{statements}: \<open>data\<close> (for
    79       datatypes), @{text fun} (stemming from code equations), also
    79       datatypes), \<open>fun\<close> (stemming from code equations), also
    80       @{text class} and @{text inst} (for type classes).
    80       \<open>class\<close> and \<open>inst\<close> (for type classes).
    81 
    81 
    82     \item Finally, the abstract program is \qn{serialised} into
    82     \item Finally, the abstract program is \qn{serialised} into
    83       concrete source code of a target language.  This step only
    83       concrete source code of a target language.  This step only
    84       produces concrete syntax but does not change the program in
    84       produces concrete syntax but does not change the program in
    85       essence; all conceptual transformations occur in the translation
    85       essence; all conceptual transformations occur in the translation
   143 
   143 
   144   \emph{Function transformers} provide a very general
   144   \emph{Function transformers} provide a very general
   145   interface, transforming a list of function theorems to another list
   145   interface, transforming a list of function theorems to another list
   146   of function theorems, provided that neither the heading constant nor
   146   of function theorems, provided that neither the heading constant nor
   147   its type change.  The @{term "0::nat"} / @{const Suc} pattern
   147   its type change.  The @{term "0::nat"} / @{const Suc} pattern
   148   used in theory @{text Code_Abstract_Nat} (see \secref{abstract_nat})
   148   used in theory \<open>Code_Abstract_Nat\<close> (see \secref{abstract_nat})
   149   uses this interface.
   149   uses this interface.
   150 
   150 
   151   \noindent The current setup of the pre- and postprocessor may be inspected
   151   \noindent The current setup of the pre- and postprocessor may be inspected
   152   using the @{command_def print_codeproc} command.  @{command_def
   152   using the @{command_def print_codeproc} command.  @{command_def
   153   code_thms} (see \secref{sec:equations}) provides a convenient
   153   code_thms} (see \secref{sec:equations}) provides a convenient
   182   "dequeue (AQueue xs (y # ys)) =
   182   "dequeue (AQueue xs (y # ys)) =
   183      (Some y, AQueue xs ys)"
   183      (Some y, AQueue xs ys)"
   184   by (cases xs, simp_all) (cases "rev xs", simp_all)
   184   by (cases xs, simp_all) (cases "rev xs", simp_all)
   185 
   185 
   186 text \<open>
   186 text \<open>
   187   \noindent The annotation @{text "[code]"} is an @{text attribute}
   187   \noindent The annotation \<open>[code]\<close> is an \<open>attribute\<close>
   188   which states that the given theorems should be considered as code
   188   which states that the given theorems should be considered as code
   189   equations for a @{text fun} statement -- the corresponding constant
   189   equations for a \<open>fun\<close> statement -- the corresponding constant
   190   is determined syntactically.  The resulting code:
   190   is determined syntactically.  The resulting code:
   191 \<close>
   191 \<close>
   192 
   192 
   193 text %quotetypewriter \<open>
   193 text %quotetypewriter \<open>
   194   @{code_stmts dequeue (consts) dequeue (Haskell)}
   194   @{code_stmts dequeue (consts) dequeue (Haskell)}
   241     else collect_duplicates (z#xs) (z#ys) zs)"
   241     else collect_duplicates (z#xs) (z#ys) zs)"
   242 
   242 
   243 text \<open>
   243 text \<open>
   244   \noindent During preprocessing, the membership test is rewritten,
   244   \noindent During preprocessing, the membership test is rewritten,
   245   resulting in @{const List.member}, which itself performs an explicit
   245   resulting in @{const List.member}, which itself performs an explicit
   246   equality check, as can be seen in the corresponding @{text SML} code:
   246   equality check, as can be seen in the corresponding \<open>SML\<close> code:
   247 \<close>
   247 \<close>
   248 
   248 
   249 text %quotetypewriter \<open>
   249 text %quotetypewriter \<open>
   250   @{code_stmts collect_duplicates (SML)}
   250   @{code_stmts collect_duplicates (SML)}
   251 \<close>
   251 \<close>
   256   explicit class @{class equal} with a corresponding operation @{const
   256   explicit class @{class equal} with a corresponding operation @{const
   257   HOL.equal} such that @{thm equal [no_vars]}.  The preprocessing
   257   HOL.equal} such that @{thm equal [no_vars]}.  The preprocessing
   258   framework does the rest by propagating the @{class equal} constraints
   258   framework does the rest by propagating the @{class equal} constraints
   259   through all dependent code equations.  For datatypes, instances of
   259   through all dependent code equations.  For datatypes, instances of
   260   @{class equal} are implicitly derived when possible.  For other types,
   260   @{class equal} are implicitly derived when possible.  For other types,
   261   you may instantiate @{text equal} manually like any other type class.
   261   you may instantiate \<open>equal\<close> manually like any other type class.
   262 \<close>
   262 \<close>
   263 
   263 
   264 
   264 
   265 subsection \<open>Explicit partiality \label{sec:partiality}\<close>
   265 subsection \<open>Explicit partiality \label{sec:partiality}\<close>
   266 
   266 
   315   constants indeed indicated a broken program; however such
   315   constants indeed indicated a broken program; however such
   316   constants can also be thought of as function definitions which always fail,
   316   constants can also be thought of as function definitions which always fail,
   317   since there is never a successful pattern match on the left hand
   317   since there is never a successful pattern match on the left hand
   318   side.  In order to categorise a constant into that category
   318   side.  In order to categorise a constant into that category
   319   explicitly, use the @{attribute code} attribute with
   319   explicitly, use the @{attribute code} attribute with
   320   @{text abort}:
   320   \<open>abort\<close>:
   321 \<close>
   321 \<close>
   322 
   322 
   323 declare %quote [[code abort: empty_queue]]
   323 declare %quote [[code abort: empty_queue]]
   324 
   324 
   325 text \<open>
   325 text \<open>