doc-src/Codegen/Thy/document/Evaluation.tex

better fudge factors for CVC3 and Yices based on Judgment Day

%
\begin{isabellebody}%
\def\isabellecontext{Evaluation}%
%
\isadelimtheory
%
\endisadelimtheory
%
\isatagtheory
\isacommand{theory}\isamarkupfalse%
\ Evaluation\isanewline
\isakeyword{imports}\ Setup\isanewline
\isakeyword{begin}%
\endisatagtheory
{\isafoldtheory}%
%
\isadelimtheory
%
\endisadelimtheory
%
\isamarkupsection{Evaluation \label{sec:evaluation}%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
Recalling \secref{sec:principle}, code generation turns a system of
  equations into a program with the \emph{same} equational semantics.
  As a consequence, this program can be used as a \emph{rewrite
  engine} for terms: rewriting a term \isa{t} using a program to a
  term \isa{t{\isaliteral{27}{\isacharprime}}} yields the theorems \isa{t\ {\isaliteral{5C3C65717569763E}{\isasymequiv}}\ t{\isaliteral{27}{\isacharprime}}}.  This
  application of code generation in the following is referred to as
  \emph{evaluation}.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsection{Evaluation techniques%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
The existing infrastructure provides a rich palette of evaluation
  techniques, each comprising different aspects:

  \begin{description}

    \item[Expressiveness.]  Depending on how good symbolic computation
      is supported, the class of terms which can be evaluated may be
      bigger or smaller.

    \item[Efficiency.]  The more machine-near the technique, the
      faster it is.

    \item[Trustability.]  Techniques which a huge (and also probably
      more configurable infrastructure) are more fragile and less
      trustable.

  \end{description}%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsubsection{The simplifier (\isa{simp})%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
The simplest way for evaluation is just using the simplifier with
  the original code equations of the underlying program.  This gives
  fully symbolic evaluation and highest trustablity, with the usual
  performance of the simplifier.  Note that for operations on abstract
  datatypes (cf.~\secref{sec:invariant}), the original theorems as
  given by the users are used, not the modified ones.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsubsection{Normalization by evaluation (\isa{nbe})%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
Normalization by evaluation \cite{Aehlig-Haftmann-Nipkow:2008:nbe}
  provides a comparably fast partially symbolic evaluation which
  permits also normalization of functions and uninterpreted symbols;
  the stack of code to be trusted is considerable.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsubsection{Evaluation in ML (\isa{code})%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
Highest performance can be achieved by evaluation in ML, at the cost
  of being restricted to ground results and a layered stack of code to
  be trusted, including code generator configurations by the user.

  Evaluation is carried out in a target language \emph{Eval} which
  inherits from \emph{SML} but for convenience uses parts of the
  Isabelle runtime environment.  The soundness of computation carried
  out there depends crucially on the correctness of the code
  generator setup; this is one of the reasons why you should not use
  adaptation (see \secref{sec:adaptation}) frivolously.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsection{Aspects of evaluation%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
Each of the techniques can be combined with different aspects.  The
  most important distinction is between dynamic and static evaluation.
  Dynamic evaluation takes the code generator configuration \qt{as it
  is} at the point where evaluation is issued.  Best example is the
  \indexdef{}{command}{value}\hypertarget{command.value}{\hyperlink{command.value}{\mbox{\isa{\isacommand{value}}}}} command which allows ad-hoc evaluation of
  terms:%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimquote
%
\endisadelimquote
%
\isatagquote
\isacommand{value}\isamarkupfalse%
\ {\isaliteral{22}{\isachardoublequoteopen}}{\isadigit{4}}{\isadigit{2}}\ {\isaliteral{2F}{\isacharslash}}\ {\isaliteral{28}{\isacharparenleft}}{\isadigit{1}}{\isadigit{2}}\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ rat{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}%
\endisatagquote
{\isafoldquote}%
%
\isadelimquote
%
\endisadelimquote
%
\begin{isamarkuptext}%
\noindent By default \hyperlink{command.value}{\mbox{\isa{\isacommand{value}}}} tries all available evaluation
  techniques and prints the result of the first succeeding one.  A particular
  technique may be specified in square brackets, e.g.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimquote
%
\endisadelimquote
%
\isatagquote
\isacommand{value}\isamarkupfalse%
\ {\isaliteral{5B}{\isacharbrackleft}}nbe{\isaliteral{5D}{\isacharbrackright}}\ {\isaliteral{22}{\isachardoublequoteopen}}{\isadigit{4}}{\isadigit{2}}\ {\isaliteral{2F}{\isacharslash}}\ {\isaliteral{28}{\isacharparenleft}}{\isadigit{1}}{\isadigit{2}}\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ rat{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}%
\endisatagquote
{\isafoldquote}%
%
\isadelimquote
%
\endisadelimquote
%
\begin{isamarkuptext}%
Static evaluation freezes the code generator configuration at a
  certain point and uses this context whenever evaluation is issued
  later on.  This is particularly appropriate for proof procedures
  which use evaluation, since then the behaviour of evaluation is not
  changed or even compromised later on by actions of the user.

  As a technical complication, terms after evaluation in ML must be
  turned into Isabelle's internal term representation again.  Since
  this is also configurable, it is never fully trusted.  For this
  reason, evaluation in ML comes with further aspects:

  \begin{description}

    \item[Plain evaluation.]  A term is normalized using the provided
      term reconstruction from ML to Isabelle; for applications which
      do not need to be fully trusted.

    \item[Property conversion.]  Evaluates propositions; since these
      are monomorphic, the term reconstruction is fixed once and for all
      and therefore trustable.

    \item[Conversion.]  Evaluates an arbitrary term \isa{t} first
      by plain evaluation and certifies the result \isa{t{\isaliteral{27}{\isacharprime}}} by
      checking the equation \isa{t\ {\isaliteral{5C3C65717569763E}{\isasymequiv}}\ t{\isaliteral{27}{\isacharprime}}} using property
      conversion.

  \end{description}

  \noindent The picture is further complicated by the roles of
  exceptions.  Here three cases have to be distinguished:

  \begin{itemize}

    \item Evaluation of \isa{t} terminates with a result \isa{t{\isaliteral{27}{\isacharprime}}}.

    \item Evaluation of \isa{t} terminates which en exception
      indicating a pattern match failure or a non-implemented
      function.  As sketched in \secref{sec:partiality}, this can be
      interpreted as partiality.
     
    \item Evaluation raises any other kind of exception.
     
  \end{itemize}

  \noindent For conversions, the first case yields the equation \isa{t\ {\isaliteral{3D}{\isacharequal}}\ t{\isaliteral{27}{\isacharprime}}}, the second defaults to reflexivity \isa{t\ {\isaliteral{3D}{\isacharequal}}\ t}.
  Exceptions of the third kind are propagated to the user.

  By default return values of plain evaluation are optional, yielding
  \isa{SOME\ t{\isaliteral{27}{\isacharprime}}} in the first case, \isa{NONE} in the
  second, and propagating the exception in the third case.  A strict
  variant of plain evaluation either yields \isa{t{\isaliteral{27}{\isacharprime}}} or propagates
  any exception, a liberal variant caputures any exception in a result
  of type \isa{Exn{\isaliteral{2E}{\isachardot}}result}.
  
  For property conversion (which coincides with conversion except for
  evaluation in ML), methods are provided which solve a given goal by
  evaluation.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsection{Schematic overview%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
\newcommand{\ttsize}{\fontsize{5.8pt}{8pt}\selectfont}
  \fontsize{9pt}{12pt}\selectfont
  \begin{tabular}{ll||c|c|c}
    & & \isa{simp} & \isa{nbe} & \isa{code} \tabularnewline \hline \hline
    \multirow{5}{1ex}{\rotatebox{90}{dynamic}}
      & interactive evaluation 
      & \hyperlink{command.value}{\mbox{\isa{\isacommand{value}}}} \isa{{\isaliteral{5B}{\isacharbrackleft}}simp{\isaliteral{5D}{\isacharbrackright}}} & \hyperlink{command.value}{\mbox{\isa{\isacommand{value}}}} \isa{{\isaliteral{5B}{\isacharbrackleft}}nbe{\isaliteral{5D}{\isacharbrackright}}} & \hyperlink{command.value}{\mbox{\isa{\isacommand{value}}}} \isa{{\isaliteral{5B}{\isacharbrackleft}}code{\isaliteral{5D}{\isacharbrackright}}}
      \tabularnewline
    & plain evaluation & & & \ttsize\verb|Code_Evaluation.dynamic_value| \tabularnewline \cline{2-5}
    & evaluation method & \hyperlink{method.code-simp}{\mbox{\isa{code{\isaliteral{5F}{\isacharunderscore}}simp}}} & \hyperlink{method.normalization}{\mbox{\isa{normalization}}} & \hyperlink{method.eval}{\mbox{\isa{eval}}} \tabularnewline
    & property conversion & & & \ttsize\verb|Code_Runtime.dynamic_holds_conv| \tabularnewline \cline{2-5}
    & conversion & \ttsize\verb|Code_Simp.dynamic_conv| & \ttsize\verb|Nbe.dynamic_conv|
      & \ttsize\verb|Code_Evaluation.dynamic_conv| \tabularnewline \hline \hline
    \multirow{3}{1ex}{\rotatebox{90}{static}}
    & plain evaluation & & & \ttsize\verb|Code_Evaluation.static_value| \tabularnewline \cline{2-5}
    & property conversion & &
      & \ttsize\verb|Code_Runtime.static_holds_conv| \tabularnewline \cline{2-5}
    & conversion & \ttsize\verb|Code_Simp.static_conv|
      & \ttsize\verb|Nbe.static_conv|
      & \ttsize\verb|Code_Evaluation.static_conv|
  \end{tabular}%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsection{Intimate connection between logic and system runtime%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
The toolbox of static evaluation conversions forms a reasonable base
  to interweave generated code and system tools.  However in some
  situations more direct interaction is desirable.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsubsection{Static embedding of generated code into system runtime -- the \isa{code} antiquotation%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
The \isa{code} antiquotation allows to include constants from
  generated code directly into ML system code, as in the following toy
  example:%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimquote
%
\endisadelimquote
%
\isatagquote
\isacommand{datatype}\isamarkupfalse%
\ form\ {\isaliteral{3D}{\isacharequal}}\ T\ {\isaliteral{7C}{\isacharbar}}\ F\ {\isaliteral{7C}{\isacharbar}}\ And\ form\ form\ {\isaliteral{7C}{\isacharbar}}\ Or\ form\ form\ %
\endisatagquote
{\isafoldquote}%
%
\isadelimquote
%
\endisadelimquote
%
\isadelimquotett
\ %
\endisadelimquotett
%
\isatagquotett
\isacommand{ML}\isamarkupfalse%
\ {\isaliteral{7B2A}{\isacharverbatimopen}}\isanewline
\ \ fun\ eval{\isaliteral{5F}{\isacharunderscore}}form\ %
\isaantiq
code\ T{}%
\endisaantiq
\ {\isaliteral{3D}{\isacharequal}}\ true\isanewline
\ \ \ \ {\isaliteral{7C}{\isacharbar}}\ eval{\isaliteral{5F}{\isacharunderscore}}form\ %
\isaantiq
code\ F{}%
\endisaantiq
\ {\isaliteral{3D}{\isacharequal}}\ false\isanewline
\ \ \ \ {\isaliteral{7C}{\isacharbar}}\ eval{\isaliteral{5F}{\isacharunderscore}}form\ {\isaliteral{28}{\isacharparenleft}}%
\isaantiq
code\ And{}%
\endisaantiq
\ {\isaliteral{28}{\isacharparenleft}}p{\isaliteral{2C}{\isacharcomma}}\ q{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline
\ \ \ \ \ \ \ \ eval{\isaliteral{5F}{\isacharunderscore}}form\ p\ andalso\ eval{\isaliteral{5F}{\isacharunderscore}}form\ q\isanewline
\ \ \ \ {\isaliteral{7C}{\isacharbar}}\ eval{\isaliteral{5F}{\isacharunderscore}}form\ {\isaliteral{28}{\isacharparenleft}}%
\isaantiq
code\ Or{}%
\endisaantiq
\ {\isaliteral{28}{\isacharparenleft}}p{\isaliteral{2C}{\isacharcomma}}\ q{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline
\ \ \ \ \ \ \ \ eval{\isaliteral{5F}{\isacharunderscore}}form\ p\ orelse\ eval{\isaliteral{5F}{\isacharunderscore}}form\ q{\isaliteral{3B}{\isacharsemicolon}}\isanewline
{\isaliteral{2A7D}{\isacharverbatimclose}}%
\endisatagquotett
{\isafoldquotett}%
%
\isadelimquotett
%
\endisadelimquotett
%
\begin{isamarkuptext}%
\noindent \isa{code} takes as argument the name of a constant;
  after the whole ML is read, the necessary code is generated
  transparently and the corresponding constant names are inserted.
  This technique also allows to use pattern matching on constructors
  stemming from compiled datatypes.  Note that the \isa{code}
  antiquotation may not refer to constants which carry adaptations;
  here you have to refer to the corresponding adapted code directly.

  For a less simplistic example, theory \isa{Approximation} in
  the \isa{Decision{\isaliteral{5F}{\isacharunderscore}}Procs} session is a good reference.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsubsection{Static embedding of generated code into system runtime -- \isa{code{\isaliteral{5F}{\isacharunderscore}}reflect}%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
The \isa{code} antiquoation is lightweight, but the generated code
  is only accessible while the ML section is processed.  Sometimes this
  is not appropriate, especially if the generated code contains datatype
  declarations which are shared with other parts of the system.  In these
  cases, \indexdef{}{command}{code\_reflect}\hypertarget{command.code-reflect}{\hyperlink{command.code-reflect}{\mbox{\isa{\isacommand{code{\isaliteral{5F}{\isacharunderscore}}reflect}}}}} can be used:%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimquote
%
\endisadelimquote
%
\isatagquote
\isacommand{code{\isaliteral{5F}{\isacharunderscore}}reflect}\isamarkupfalse%
\ Sum{\isaliteral{5F}{\isacharunderscore}}Type\isanewline
\ \ \isakeyword{datatypes}\ sum\ {\isaliteral{3D}{\isacharequal}}\ Inl\ {\isaliteral{7C}{\isacharbar}}\ Inr\isanewline
\ \ \isakeyword{functions}\ {\isaliteral{22}{\isachardoublequoteopen}}Sum{\isaliteral{5F}{\isacharunderscore}}Type{\isaliteral{2E}{\isachardot}}Projl{\isaliteral{22}{\isachardoublequoteclose}}\ {\isaliteral{22}{\isachardoublequoteopen}}Sum{\isaliteral{5F}{\isacharunderscore}}Type{\isaliteral{2E}{\isachardot}}Projr{\isaliteral{22}{\isachardoublequoteclose}}%
\endisatagquote
{\isafoldquote}%
%
\isadelimquote
%
\endisadelimquote
%
\begin{isamarkuptext}%
\noindent \indexdef{}{command}{code\_reflect}\hypertarget{command.code-reflect}{\hyperlink{command.code-reflect}{\mbox{\isa{\isacommand{code{\isaliteral{5F}{\isacharunderscore}}reflect}}}}} takes a structure name and
  references to datatypes and functions; for these code is compiled
  into the named ML structure and the \emph{Eval} target is modified
  in a way that future code generation will reference these
  precompiled versions of the given datatypes and functions.  This
  also allows to refer to the referenced datatypes and functions from
  arbitrary ML code as well.

  A typical example for \hyperlink{command.code-reflect}{\mbox{\isa{\isacommand{code{\isaliteral{5F}{\isacharunderscore}}reflect}}}} can be found in the
  \hyperlink{theory.Predicate}{\mbox{\isa{Predicate}}} theory.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isamarkupsubsubsection{Separate compilation -- \isa{code{\isaliteral{5F}{\isacharunderscore}}reflect}%
}
\isamarkuptrue%
%
\begin{isamarkuptext}%
For technical reasons it is sometimes necessary to separate
  generation and compilation of code which is supposed to be used in
  the system runtime.  For this \hyperlink{command.code-reflect}{\mbox{\isa{\isacommand{code{\isaliteral{5F}{\isacharunderscore}}reflect}}}} with an
  optional \isa{file} argument can be used:%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimquote
%
\endisadelimquote
%
\isatagquote
\isacommand{code{\isaliteral{5F}{\isacharunderscore}}reflect}\isamarkupfalse%
\ Rat\isanewline
\ \ \isakeyword{datatypes}\ rat\ {\isaliteral{3D}{\isacharequal}}\ Frct\isanewline
\ \ \isakeyword{functions}\ Fract\isanewline
\ \ \ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{28}{\isacharparenleft}}plus\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}\ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{28}{\isacharparenleft}}minus\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}\isanewline
\ \ \ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{28}{\isacharparenleft}}times\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}\ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{28}{\isacharparenleft}}divide\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ rat{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}\isanewline
\ \ \isakeyword{file}\ {\isaliteral{22}{\isachardoublequoteopen}}examples{\isaliteral{2F}{\isacharslash}}rat{\isaliteral{2E}{\isachardot}}ML{\isaliteral{22}{\isachardoublequoteclose}}%
\endisatagquote
{\isafoldquote}%
%
\isadelimquote
%
\endisadelimquote
%
\begin{isamarkuptext}%
\noindent This merely generates the referenced code to the given
  file which can be included into the system runtime later on.%
\end{isamarkuptext}%
\isamarkuptrue%
%
\isadelimtheory
%
\endisadelimtheory
%
\isatagtheory
\isacommand{end}\isamarkupfalse%
%
\endisatagtheory
{\isafoldtheory}%
%
\isadelimtheory
%
\endisadelimtheory
\isanewline
\end{isabellebody}%
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "root"
%%% End: