doc-src/TutorialI/Misc/document/simp.tex
changeset 10397 e2d0dda41f2c
parent 10396 5ab08609e6c8
child 10589 b2d1b393b750
equal deleted inserted replaced
10396:5ab08609e6c8 10397:e2d0dda41f2c
     1 %
     1 %
     2 \begin{isabellebody}%
     2 \begin{isabellebody}%
     3 \def\isabellecontext{simp}%
     3 \def\isabellecontext{simp}%
     4 %
     4 %
     5 \isamarkupsubsubsection{Simplification rules}
     5 \isamarkupsubsubsection{Simplification rules%
       
     6 }
     6 %
     7 %
     7 \begin{isamarkuptext}%
     8 \begin{isamarkuptext}%
     8 \indexbold{simplification rule}
     9 \indexbold{simplification rule}
     9 To facilitate simplification, theorems can be declared to be simplification
    10 To facilitate simplification, theorems can be declared to be simplification
    10 rules (with the help of the attribute \isa{{\isacharbrackleft}simp{\isacharbrackright}}\index{*simp
    11 rules (with the help of the attribute \isa{{\isacharbrackleft}simp{\isacharbrackright}}\index{*simp
    37   to include simplification rules that can lead to nontermination, either on
    38   to include simplification rules that can lead to nontermination, either on
    38   their own or in combination with other simplification rules.
    39   their own or in combination with other simplification rules.
    39 \end{warn}%
    40 \end{warn}%
    40 \end{isamarkuptext}%
    41 \end{isamarkuptext}%
    41 %
    42 %
    42 \isamarkupsubsubsection{The simplification method}
    43 \isamarkupsubsubsection{The simplification method%
       
    44 }
    43 %
    45 %
    44 \begin{isamarkuptext}%
    46 \begin{isamarkuptext}%
    45 \index{*simp (method)|bold}
    47 \index{*simp (method)|bold}
    46 The general format of the simplification method is
    48 The general format of the simplification method is
    47 \begin{quote}
    49 \begin{quote}
    53 only the first subgoal and may thus need to be repeated---use
    55 only the first subgoal and may thus need to be repeated---use
    54 \isaindex{simp_all} to simplify all subgoals.
    56 \isaindex{simp_all} to simplify all subgoals.
    55 Note that \isa{simp} fails if nothing changes.%
    57 Note that \isa{simp} fails if nothing changes.%
    56 \end{isamarkuptext}%
    58 \end{isamarkuptext}%
    57 %
    59 %
    58 \isamarkupsubsubsection{Adding and deleting simplification rules}
    60 \isamarkupsubsubsection{Adding and deleting simplification rules%
       
    61 }
    59 %
    62 %
    60 \begin{isamarkuptext}%
    63 \begin{isamarkuptext}%
    61 If a certain theorem is merely needed in a few proofs by simplification,
    64 If a certain theorem is merely needed in a few proofs by simplification,
    62 we do not need to make it a global simplification rule. Instead we can modify
    65 we do not need to make it a global simplification rule. Instead we can modify
    63 the set of simplification rules used in a simplification step by adding rules
    66 the set of simplification rules used in a simplification step by adding rules
    71 \begin{quote}
    74 \begin{quote}
    72 \isa{only{\isacharcolon}} \textit{list of theorem names}
    75 \isa{only{\isacharcolon}} \textit{list of theorem names}
    73 \end{quote}%
    76 \end{quote}%
    74 \end{isamarkuptext}%
    77 \end{isamarkuptext}%
    75 %
    78 %
    76 \isamarkupsubsubsection{Assumptions}
    79 \isamarkupsubsubsection{Assumptions%
       
    80 }
    77 %
    81 %
    78 \begin{isamarkuptext}%
    82 \begin{isamarkuptext}%
    79 \index{simplification!with/of assumptions}
    83 \index{simplification!with/of assumptions}
    80 By default, assumptions are part of the simplification process: they are used
    84 By default, assumptions are part of the simplification process: they are used
    81 as simplification rules and are simplified themselves. For example:%
    85 as simplification rules and are simplified themselves. For example:%
   121 
   125 
   122 Note that only one of the above options is allowed, and it must precede all
   126 Note that only one of the above options is allowed, and it must precede all
   123 other arguments.%
   127 other arguments.%
   124 \end{isamarkuptext}%
   128 \end{isamarkuptext}%
   125 %
   129 %
   126 \isamarkupsubsubsection{Rewriting with definitions}
   130 \isamarkupsubsubsection{Rewriting with definitions%
       
   131 }
   127 %
   132 %
   128 \begin{isamarkuptext}%
   133 \begin{isamarkuptext}%
   129 \index{simplification!with definitions}
   134 \index{simplification!with definitions}
   130 Constant definitions (\S\ref{sec:ConstDefinitions}) can
   135 Constant definitions (\S\ref{sec:ConstDefinitions}) can
   131 be used as simplification rules, but by default they are not.  Hence the
   136 be used as simplification rules, but by default they are not.  Hence the
   169   occurrences of $f$ with at least two arguments. Thus it is safer to define
   174   occurrences of $f$ with at least two arguments. Thus it is safer to define
   170   $f$~\isasymequiv~\isasymlambda$x\,y.\;t$.
   175   $f$~\isasymequiv~\isasymlambda$x\,y.\;t$.
   171 \end{warn}%
   176 \end{warn}%
   172 \end{isamarkuptext}%
   177 \end{isamarkuptext}%
   173 %
   178 %
   174 \isamarkupsubsubsection{Simplifying let-expressions}
   179 \isamarkupsubsubsection{Simplifying let-expressions%
       
   180 }
   175 %
   181 %
   176 \begin{isamarkuptext}%
   182 \begin{isamarkuptext}%
   177 \index{simplification!of let-expressions}
   183 \index{simplification!of let-expressions}
   178 Proving a goal containing \isaindex{let}-expressions almost invariably
   184 Proving a goal containing \isaindex{let}-expressions almost invariably
   179 requires the \isa{let}-con\-structs to be expanded at some point. Since
   185 requires the \isa{let}-con\-structs to be expanded at some point. Since
   188 If, in a particular context, there is no danger of a combinatorial explosion
   194 If, in a particular context, there is no danger of a combinatorial explosion
   189 of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by
   195 of nested \isa{let}s one could even simlify with \isa{Let{\isacharunderscore}def} by
   190 default:%
   196 default:%
   191 \end{isamarkuptext}%
   197 \end{isamarkuptext}%
   192 \isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}%
   198 \isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}%
   193 \isamarkupsubsubsection{Conditional equations}
   199 \isamarkupsubsubsection{Conditional equations%
       
   200 }
   194 %
   201 %
   195 \begin{isamarkuptext}%
   202 \begin{isamarkuptext}%
   196 So far all examples of rewrite rules were equations. The simplifier also
   203 So far all examples of rewrite rules were equations. The simplifier also
   197 accepts \emph{conditional} equations, for example%
   204 accepts \emph{conditional} equations, for example%
   198 \end{isamarkuptext}%
   205 \end{isamarkuptext}%
   215 because the corresponding precondition \isa{rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}
   222 because the corresponding precondition \isa{rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}
   216 simplifies to \isa{xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}, which is exactly the local
   223 simplifies to \isa{xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}}, which is exactly the local
   217 assumption of the subgoal.%
   224 assumption of the subgoal.%
   218 \end{isamarkuptext}%
   225 \end{isamarkuptext}%
   219 %
   226 %
   220 \isamarkupsubsubsection{Automatic case splits}
   227 \isamarkupsubsubsection{Automatic case splits%
       
   228 }
   221 %
   229 %
   222 \begin{isamarkuptext}%
   230 \begin{isamarkuptext}%
   223 \indexbold{case splits}\index{*split|(}
   231 \indexbold{case splits}\index{*split|(}
   224 Goals containing \isa{if}-expressions are usually proved by case
   232 Goals containing \isa{if}-expressions are usually proved by case
   225 distinction on the condition of the \isa{if}. For example the goal%
   233 distinction on the condition of the \isa{if}. For example the goal%
   308 \end{warn}
   316 \end{warn}
   309 
   317 
   310 \index{*split|)}%
   318 \index{*split|)}%
   311 \end{isamarkuptxt}%
   319 \end{isamarkuptxt}%
   312 %
   320 %
   313 \isamarkupsubsubsection{Arithmetic}
   321 \isamarkupsubsubsection{Arithmetic%
       
   322 }
   314 %
   323 %
   315 \begin{isamarkuptext}%
   324 \begin{isamarkuptext}%
   316 \index{arithmetic}
   325 \index{arithmetic}
   317 The simplifier routinely solves a small class of linear arithmetic formulae
   326 The simplifier routinely solves a small class of linear arithmetic formulae
   318 (over type \isa{nat} and other numeric types): it only takes into account
   327 (over type \isa{nat} and other numeric types): it only takes into account
   328 \begin{isamarkuptext}%
   337 \begin{isamarkuptext}%
   329 \noindent
   338 \noindent
   330 is not proved by simplification and requires \isa{arith}.%
   339 is not proved by simplification and requires \isa{arith}.%
   331 \end{isamarkuptext}%
   340 \end{isamarkuptext}%
   332 %
   341 %
   333 \isamarkupsubsubsection{Tracing}
   342 \isamarkupsubsubsection{Tracing%
       
   343 }
   334 %
   344 %
   335 \begin{isamarkuptext}%
   345 \begin{isamarkuptext}%
   336 \indexbold{tracing the simplifier}
   346 \indexbold{tracing the simplifier}
   337 Using the simplifier effectively may take a bit of experimentation.  Set the
   347 Using the simplifier effectively may take a bit of experimentation.  Set the
   338 \isaindexbold{trace_simp} \rmindex{flag} to get a better idea of what is going
   348 \isaindexbold{trace_simp} \rmindex{flag} to get a better idea of what is going