doc-src/TutorialI/Misc/document/simp.tex
changeset 17175 1eced27ee0e1
parent 17056 05fc32a23b8b
child 17181 5f42dd5e6570
equal deleted inserted replaced
17174:11aa41ed306d 17175:1eced27ee0e1
     5 \isadelimtheory
     5 \isadelimtheory
     6 %
     6 %
     7 \endisadelimtheory
     7 \endisadelimtheory
     8 %
     8 %
     9 \isatagtheory
     9 \isatagtheory
       
    10 \isamarkupfalse%
    10 %
    11 %
    11 \endisatagtheory
    12 \endisatagtheory
    12 {\isafoldtheory}%
    13 {\isafoldtheory}%
    13 %
    14 %
    14 \isadelimtheory
    15 \isadelimtheory
    15 %
    16 %
    16 \endisadelimtheory
    17 \endisadelimtheory
    17 \isamarkuptrue%
       
    18 %
    18 %
    19 \isamarkupsubsection{Simplification Rules%
    19 \isamarkupsubsection{Simplification Rules%
    20 }
    20 }
    21 \isamarkuptrue%
    21 \isamarkuptrue%
    22 %
    22 %
   122 \begin{isamarkuptext}%
   122 \begin{isamarkuptext}%
   123 \index{simplification!with/of assumptions}
   123 \index{simplification!with/of assumptions}
   124 By default, assumptions are part of the simplification process: they are used
   124 By default, assumptions are part of the simplification process: they are used
   125 as simplification rules and are simplified themselves. For example:%
   125 as simplification rules and are simplified themselves. For example:%
   126 \end{isamarkuptext}%
   126 \end{isamarkuptext}%
   127 \isamarkupfalse%
   127 \isamarkuptrue%
   128 \isacommand{lemma}\ {\isachardoublequote}{\isasymlbrakk}\ xs\ {\isacharat}\ zs\ {\isacharequal}\ ys\ {\isacharat}\ xs{\isacharsemicolon}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ ys\ {\isacharequal}\ zs{\isachardoublequote}\isanewline
   128 \isacommand{lemma}\isamarkupfalse%
   129 %
   129 \ {\isachardoublequoteopen}{\isasymlbrakk}\ xs\ {\isacharat}\ zs\ {\isacharequal}\ ys\ {\isacharat}\ xs{\isacharsemicolon}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ ys\ {\isacharequal}\ zs{\isachardoublequoteclose}\isanewline
   130 \isadelimproof
   130 %
   131 %
   131 \isadelimproof
   132 \endisadelimproof
   132 %
   133 %
   133 \endisadelimproof
   134 \isatagproof
   134 %
   135 \isamarkupfalse%
   135 \isatagproof
   136 \isacommand{apply}\ simp\isanewline
   136 \isacommand{apply}\isamarkupfalse%
   137 \isamarkupfalse%
   137 \ simp\isanewline
   138 \isacommand{done}%
   138 \isacommand{done}\isamarkupfalse%
   139 \endisatagproof
   139 %
   140 {\isafoldproof}%
   140 \endisatagproof
   141 %
   141 {\isafoldproof}%
   142 \isadelimproof
   142 %
   143 %
   143 \isadelimproof
   144 \endisadelimproof
   144 %
   145 \isamarkuptrue%
   145 \endisadelimproof
   146 %
   146 %
   147 \begin{isamarkuptext}%
   147 \begin{isamarkuptext}%
   148 \noindent
   148 \noindent
   149 The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn
   149 The second assumption simplifies to \isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}, which in turn
   150 simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the
   150 simplifies the first assumption to \isa{zs\ {\isacharequal}\ ys}, thus reducing the
   151 conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}.
   151 conclusion to \isa{ys\ {\isacharequal}\ ys} and hence to \isa{True}.
   152 
   152 
   153 In some cases, using the assumptions can lead to nontermination:%
   153 In some cases, using the assumptions can lead to nontermination:%
   154 \end{isamarkuptext}%
   154 \end{isamarkuptext}%
   155 \isamarkupfalse%
   155 \isamarkuptrue%
   156 \isacommand{lemma}\ {\isachardoublequote}{\isasymforall}x{\isachardot}\ f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}%
   156 \isacommand{lemma}\isamarkupfalse%
   157 \isadelimproof
   157 \ {\isachardoublequoteopen}{\isasymforall}x{\isachardot}\ f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}\ {\isasymLongrightarrow}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ f\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}%
   158 %
   158 \isadelimproof
   159 \endisadelimproof
   159 %
   160 %
   160 \endisadelimproof
   161 \isatagproof
   161 %
   162 \isamarkuptrue%
   162 \isatagproof
   163 %
   163 %
   164 \begin{isamarkuptxt}%
   164 \begin{isamarkuptxt}%
   165 \noindent
   165 \noindent
   166 An unmodified application of \isa{simp} loops.  The culprit is the
   166 An unmodified application of \isa{simp} loops.  The culprit is the
   167 simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}}, which is extracted from
   167 simplification rule \isa{f\ x\ {\isacharequal}\ g\ {\isacharparenleft}f\ {\isacharparenleft}g\ x{\isacharparenright}{\isacharparenright}}, which is extracted from
   168 the assumption.  (Isabelle notices certain simple forms of
   168 the assumption.  (Isabelle notices certain simple forms of
   169 nontermination but not this one.)  The problem can be circumvented by
   169 nontermination but not this one.)  The problem can be circumvented by
   170 telling the simplifier to ignore the assumptions:%
   170 telling the simplifier to ignore the assumptions:%
   171 \end{isamarkuptxt}%
   171 \end{isamarkuptxt}%
   172 \isamarkupfalse%
   172 \isamarkuptrue%
   173 \isacommand{apply}{\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}\isanewline
   173 \isacommand{apply}\isamarkupfalse%
   174 \isamarkupfalse%
   174 {\isacharparenleft}simp\ {\isacharparenleft}no{\isacharunderscore}asm{\isacharparenright}{\isacharparenright}\isanewline
   175 \isacommand{done}%
   175 \isacommand{done}\isamarkupfalse%
   176 \endisatagproof
   176 %
   177 {\isafoldproof}%
   177 \endisatagproof
   178 %
   178 {\isafoldproof}%
   179 \isadelimproof
   179 %
   180 %
   180 \isadelimproof
   181 \endisadelimproof
   181 %
   182 \isamarkuptrue%
   182 \endisadelimproof
   183 %
   183 %
   184 \begin{isamarkuptext}%
   184 \begin{isamarkuptext}%
   185 \noindent
   185 \noindent
   186 Three modifiers influence the treatment of assumptions:
   186 Three modifiers influence the treatment of assumptions:
   187 \begin{description}
   187 \begin{description}
   225 proofs more robust: if the definition has to be changed,
   225 proofs more robust: if the definition has to be changed,
   226 only the proofs of the abstract properties will be affected.
   226 only the proofs of the abstract properties will be affected.
   227 
   227 
   228 For example, given%
   228 For example, given%
   229 \end{isamarkuptext}%
   229 \end{isamarkuptext}%
   230 \isamarkupfalse%
   230 \isamarkuptrue%
   231 \isacommand{constdefs}\ xor\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}bool\ {\isasymRightarrow}\ bool\ {\isasymRightarrow}\ bool{\isachardoublequote}\isanewline
   231 \isacommand{constdefs}\isamarkupfalse%
   232 \ \ \ \ \ \ \ \ \ {\isachardoublequote}xor\ A\ B\ {\isasymequiv}\ {\isacharparenleft}A\ {\isasymand}\ {\isasymnot}B{\isacharparenright}\ {\isasymor}\ {\isacharparenleft}{\isasymnot}A\ {\isasymand}\ B{\isacharparenright}{\isachardoublequote}\isamarkuptrue%
   232 \ xor\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}bool\ {\isasymRightarrow}\ bool\ {\isasymRightarrow}\ bool{\isachardoublequoteclose}\isanewline
   233 %
   233 \ \ \ \ \ \ \ \ \ {\isachardoublequoteopen}xor\ A\ B\ {\isasymequiv}\ {\isacharparenleft}A\ {\isasymand}\ {\isasymnot}B{\isacharparenright}\ {\isasymor}\ {\isacharparenleft}{\isasymnot}A\ {\isasymand}\ B{\isacharparenright}{\isachardoublequoteclose}%
   234 \begin{isamarkuptext}%
   234 \begin{isamarkuptext}%
   235 \noindent
   235 \noindent
   236 we may want to prove%
   236 we may want to prove%
   237 \end{isamarkuptext}%
   237 \end{isamarkuptext}%
   238 \isamarkupfalse%
   238 \isamarkuptrue%
   239 \isacommand{lemma}\ {\isachardoublequote}xor\ A\ {\isacharparenleft}{\isasymnot}A{\isacharparenright}{\isachardoublequote}%
   239 \isacommand{lemma}\isamarkupfalse%
   240 \isadelimproof
   240 \ {\isachardoublequoteopen}xor\ A\ {\isacharparenleft}{\isasymnot}A{\isacharparenright}{\isachardoublequoteclose}%
   241 %
   241 \isadelimproof
   242 \endisadelimproof
   242 %
   243 %
   243 \endisadelimproof
   244 \isatagproof
   244 %
   245 \isamarkuptrue%
   245 \isatagproof
   246 %
   246 %
   247 \begin{isamarkuptxt}%
   247 \begin{isamarkuptxt}%
   248 \noindent
   248 \noindent
   249 Typically, we begin by unfolding some definitions:
   249 Typically, we begin by unfolding some definitions:
   250 \indexbold{definitions!unfolding}%
   250 \indexbold{definitions!unfolding}%
   251 \end{isamarkuptxt}%
   251 \end{isamarkuptxt}%
   252 \isamarkupfalse%
   252 \isamarkuptrue%
   253 \isacommand{apply}{\isacharparenleft}simp\ only{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}\isamarkuptrue%
   253 \isacommand{apply}\isamarkupfalse%
   254 %
   254 {\isacharparenleft}simp\ only{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}%
   255 \begin{isamarkuptxt}%
   255 \begin{isamarkuptxt}%
   256 \noindent
   256 \noindent
   257 In this particular case, the resulting goal
   257 In this particular case, the resulting goal
   258 \begin{isabelle}%
   258 \begin{isabelle}%
   259 \ {\isadigit{1}}{\isachardot}\ A\ {\isasymand}\ {\isasymnot}\ {\isasymnot}\ A\ {\isasymor}\ {\isasymnot}\ A\ {\isasymand}\ {\isasymnot}\ A%
   259 \ {\isadigit{1}}{\isachardot}\ A\ {\isasymand}\ {\isasymnot}\ {\isasymnot}\ A\ {\isasymor}\ {\isasymnot}\ A\ {\isasymand}\ {\isasymnot}\ A%
   260 \end{isabelle}
   260 \end{isabelle}
   261 can be proved by simplification. Thus we could have proved the lemma outright by%
   261 can be proved by simplification. Thus we could have proved the lemma outright by%
   262 \end{isamarkuptxt}%
   262 \end{isamarkuptxt}%
   263 %
   263 \isamarkuptrue%
   264 \endisatagproof
   264 \isamarkupfalse%
   265 {\isafoldproof}%
   265 %
   266 %
   266 \endisatagproof
   267 \isadelimproof
   267 {\isafoldproof}%
   268 %
   268 %
   269 \endisadelimproof
   269 \isadelimproof
   270 %
   270 %
   271 \isadelimproof
   271 \endisadelimproof
   272 %
   272 \isamarkupfalse%
   273 \endisadelimproof
   273 %
   274 %
   274 \isadelimproof
   275 \isatagproof
   275 %
   276 \isamarkupfalse%
   276 \endisadelimproof
   277 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}%
   277 %
   278 \endisatagproof
   278 \isatagproof
   279 {\isafoldproof}%
   279 \isacommand{apply}\isamarkupfalse%
   280 %
   280 {\isacharparenleft}simp\ add{\isacharcolon}\ xor{\isacharunderscore}def{\isacharparenright}\isamarkupfalse%
   281 \isadelimproof
   281 %
   282 %
   282 \endisatagproof
   283 \endisadelimproof
   283 {\isafoldproof}%
   284 \isamarkuptrue%
   284 %
       
   285 \isadelimproof
       
   286 %
       
   287 \endisadelimproof
   285 %
   288 %
   286 \begin{isamarkuptext}%
   289 \begin{isamarkuptext}%
   287 \noindent
   290 \noindent
   288 Of course we can also unfold definitions in the middle of a proof.
   291 Of course we can also unfold definitions in the middle of a proof.
   289 
   292 
   312 \isa{let}-con\-structs to be expanded at some point. Since
   315 \isa{let}-con\-structs to be expanded at some point. Since
   313 \isa{let}\ldots\isa{=}\ldots\isa{in}{\ldots} is just syntactic sugar for
   316 \isa{let}\ldots\isa{=}\ldots\isa{in}{\ldots} is just syntactic sugar for
   314 the predefined constant \isa{Let}, expanding \isa{let}-constructs
   317 the predefined constant \isa{Let}, expanding \isa{let}-constructs
   315 means rewriting with \tdx{Let_def}:%
   318 means rewriting with \tdx{Let_def}:%
   316 \end{isamarkuptext}%
   319 \end{isamarkuptext}%
   317 \isamarkupfalse%
   320 \isamarkuptrue%
   318 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequote}\isanewline
   321 \isacommand{lemma}\isamarkupfalse%
   319 %
   322 \ {\isachardoublequoteopen}{\isacharparenleft}let\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ in\ xs{\isacharat}ys{\isacharat}xs{\isacharparenright}\ {\isacharequal}\ ys{\isachardoublequoteclose}\isanewline
   320 \isadelimproof
   323 %
   321 %
   324 \isadelimproof
   322 \endisadelimproof
   325 %
   323 %
   326 \endisadelimproof
   324 \isatagproof
   327 %
   325 \isamarkupfalse%
   328 \isatagproof
   326 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}\isanewline
   329 \isacommand{apply}\isamarkupfalse%
   327 \isamarkupfalse%
   330 {\isacharparenleft}simp\ add{\isacharcolon}\ Let{\isacharunderscore}def{\isacharparenright}\isanewline
   328 \isacommand{done}%
   331 \isacommand{done}\isamarkupfalse%
   329 \endisatagproof
   332 %
   330 {\isafoldproof}%
   333 \endisatagproof
   331 %
   334 {\isafoldproof}%
   332 \isadelimproof
   335 %
   333 %
   336 \isadelimproof
   334 \endisadelimproof
   337 %
   335 \isamarkuptrue%
   338 \endisadelimproof
   336 %
   339 %
   337 \begin{isamarkuptext}%
   340 \begin{isamarkuptext}%
   338 If, in a particular context, there is no danger of a combinatorial explosion
   341 If, in a particular context, there is no danger of a combinatorial explosion
   339 of nested \isa{let}s, you could even simplify with \isa{Let{\isacharunderscore}def} by
   342 of nested \isa{let}s, you could even simplify with \isa{Let{\isacharunderscore}def} by
   340 default:%
   343 default:%
   341 \end{isamarkuptext}%
   344 \end{isamarkuptext}%
   342 \isamarkupfalse%
   345 \isamarkuptrue%
   343 \isacommand{declare}\ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}\isamarkuptrue%
   346 \isacommand{declare}\isamarkupfalse%
   344 %
   347 \ Let{\isacharunderscore}def\ {\isacharbrackleft}simp{\isacharbrackright}%
   345 \isamarkupsubsection{Conditional Simplification Rules%
   348 \isamarkupsubsection{Conditional Simplification Rules%
   346 }
   349 }
   347 \isamarkuptrue%
   350 \isamarkuptrue%
   348 %
   351 %
   349 \begin{isamarkuptext}%
   352 \begin{isamarkuptext}%
   350 \index{conditional simplification rules}%
   353 \index{conditional simplification rules}%
   351 So far all examples of rewrite rules were equations. The simplifier also
   354 So far all examples of rewrite rules were equations. The simplifier also
   352 accepts \emph{conditional} equations, for example%
   355 accepts \emph{conditional} equations, for example%
   353 \end{isamarkuptext}%
   356 \end{isamarkuptext}%
   354 \isamarkupfalse%
   357 \isamarkuptrue%
   355 \isacommand{lemma}\ hd{\isacharunderscore}Cons{\isacharunderscore}tl{\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ \ {\isasymLongrightarrow}\ \ hd\ xs\ {\isacharhash}\ tl\ xs\ {\isacharequal}\ xs{\isachardoublequote}\isanewline
   358 \isacommand{lemma}\isamarkupfalse%
   356 %
   359 \ hd{\isacharunderscore}Cons{\isacharunderscore}tl{\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequoteopen}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ \ {\isasymLongrightarrow}\ \ hd\ xs\ {\isacharhash}\ tl\ xs\ {\isacharequal}\ xs{\isachardoublequoteclose}\isanewline
   357 \isadelimproof
   360 %
   358 %
   361 \isadelimproof
   359 \endisadelimproof
   362 %
   360 %
   363 \endisadelimproof
   361 \isatagproof
   364 %
   362 \isamarkupfalse%
   365 \isatagproof
   363 \isacommand{apply}{\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}\isanewline
   366 \isacommand{apply}\isamarkupfalse%
   364 \isamarkupfalse%
   367 {\isacharparenleft}case{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharcomma}\ simp{\isacharparenright}\isanewline
   365 \isacommand{done}%
   368 \isacommand{done}\isamarkupfalse%
   366 \endisatagproof
   369 %
   367 {\isafoldproof}%
   370 \endisatagproof
   368 %
   371 {\isafoldproof}%
   369 \isadelimproof
   372 %
   370 %
   373 \isadelimproof
   371 \endisadelimproof
   374 %
   372 \isamarkuptrue%
   375 \endisadelimproof
   373 %
   376 %
   374 \begin{isamarkuptext}%
   377 \begin{isamarkuptext}%
   375 \noindent
   378 \noindent
   376 Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a
   379 Note the use of ``\ttindexboldpos{,}{$Isar}'' to string together a
   377 sequence of methods. Assuming that the simplification rule
   380 sequence of methods. Assuming that the simplification rule
   378 \isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}}
   381 \isa{{\isacharparenleft}rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}}
   379 is present as well,
   382 is present as well,
   380 the lemma below is proved by plain simplification:%
   383 the lemma below is proved by plain simplification:%
   381 \end{isamarkuptext}%
   384 \end{isamarkuptext}%
   382 \isamarkupfalse%
   385 \isamarkuptrue%
   383 \isacommand{lemma}\ {\isachardoublequote}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ hd{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ rev\ xs{\isachardoublequote}%
   386 \isacommand{lemma}\isamarkupfalse%
   384 \isadelimproof
   387 \ {\isachardoublequoteopen}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ hd{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ rev\ xs{\isachardoublequoteclose}%
   385 %
   388 \isadelimproof
   386 \endisadelimproof
   389 %
   387 %
   390 \endisadelimproof
   388 \isatagproof
   391 %
   389 %
   392 \isatagproof
   390 \endisatagproof
   393 \isamarkupfalse%
   391 {\isafoldproof}%
   394 %
   392 %
   395 \endisatagproof
   393 \isadelimproof
   396 {\isafoldproof}%
   394 %
   397 %
   395 \endisadelimproof
   398 \isadelimproof
   396 \isamarkuptrue%
   399 %
       
   400 \endisadelimproof
   397 %
   401 %
   398 \begin{isamarkuptext}%
   402 \begin{isamarkuptext}%
   399 \noindent
   403 \noindent
   400 The conditional equation \isa{hd{\isacharunderscore}Cons{\isacharunderscore}tl} above
   404 The conditional equation \isa{hd{\isacharunderscore}Cons{\isacharunderscore}tl} above
   401 can simplify \isa{hd\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl\ {\isacharparenleft}rev\ xs{\isacharparenright}} to \isa{rev\ xs}
   405 can simplify \isa{hd\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharhash}\ tl\ {\isacharparenleft}rev\ xs{\isacharparenright}} to \isa{rev\ xs}
   413 \label{sec:AutoCaseSplits}\indexbold{case splits}%
   417 \label{sec:AutoCaseSplits}\indexbold{case splits}%
   414 Goals containing \isa{if}-expressions\index{*if expressions!splitting of}
   418 Goals containing \isa{if}-expressions\index{*if expressions!splitting of}
   415 are usually proved by case
   419 are usually proved by case
   416 distinction on the boolean condition.  Here is an example:%
   420 distinction on the boolean condition.  Here is an example:%
   417 \end{isamarkuptext}%
   421 \end{isamarkuptext}%
   418 \isamarkupfalse%
   422 \isamarkuptrue%
   419 \isacommand{lemma}\ {\isachardoublequote}{\isasymforall}xs{\isachardot}\ if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ else\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}%
   423 \isacommand{lemma}\isamarkupfalse%
   420 \isadelimproof
   424 \ {\isachardoublequoteopen}{\isasymforall}xs{\isachardot}\ if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ else\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}%
   421 %
   425 \isadelimproof
   422 \endisadelimproof
   426 %
   423 %
   427 \endisadelimproof
   424 \isatagproof
   428 %
   425 \isamarkuptrue%
   429 \isatagproof
   426 %
   430 %
   427 \begin{isamarkuptxt}%
   431 \begin{isamarkuptxt}%
   428 \noindent
   432 \noindent
   429 The goal can be split by a special method, \methdx{split}:%
   433 The goal can be split by a special method, \methdx{split}:%
   430 \end{isamarkuptxt}%
   434 \end{isamarkuptxt}%
   431 \isamarkupfalse%
   435 \isamarkuptrue%
   432 \isacommand{apply}{\isacharparenleft}split\ split{\isacharunderscore}if{\isacharparenright}\isamarkuptrue%
   436 \isacommand{apply}\isamarkupfalse%
   433 %
   437 {\isacharparenleft}split\ split{\isacharunderscore}if{\isacharparenright}%
   434 \begin{isamarkuptxt}%
   438 \begin{isamarkuptxt}%
   435 \noindent
   439 \noindent
   436 \begin{isabelle}%
   440 \begin{isabelle}%
   437 \ {\isadigit{1}}{\isachardot}\ {\isasymforall}xs{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}%
   441 \ {\isadigit{1}}{\isachardot}\ {\isasymforall}xs{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ rev\ xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}%
   438 \end{isabelle}
   442 \end{isabelle}
   443 on the initial goal above.
   447 on the initial goal above.
   444 
   448 
   445 This splitting idea generalizes from \isa{if} to \sdx{case}.
   449 This splitting idea generalizes from \isa{if} to \sdx{case}.
   446 Let us simplify a case analysis over lists:\index{*list.split (theorem)}%
   450 Let us simplify a case analysis over lists:\index{*list.split (theorem)}%
   447 \end{isamarkuptxt}%
   451 \end{isamarkuptxt}%
   448 %
   452 \isamarkuptrue%
   449 \endisatagproof
   453 \isamarkupfalse%
   450 {\isafoldproof}%
   454 %
   451 %
   455 \endisatagproof
   452 \isadelimproof
   456 {\isafoldproof}%
   453 %
   457 %
   454 \endisadelimproof
   458 \isadelimproof
   455 \isamarkupfalse%
   459 %
   456 \isacommand{lemma}\ {\isachardoublequote}{\isacharparenleft}case\ xs\ of\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymRightarrow}\ zs\ {\isacharbar}\ y{\isacharhash}ys\ {\isasymRightarrow}\ y{\isacharhash}{\isacharparenleft}ys{\isacharat}zs{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ xs{\isacharat}zs{\isachardoublequote}\isanewline
   460 \endisadelimproof
   457 %
   461 \isacommand{lemma}\isamarkupfalse%
   458 \isadelimproof
   462 \ {\isachardoublequoteopen}{\isacharparenleft}case\ xs\ of\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymRightarrow}\ zs\ {\isacharbar}\ y{\isacharhash}ys\ {\isasymRightarrow}\ y{\isacharhash}{\isacharparenleft}ys{\isacharat}zs{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ xs{\isacharat}zs{\isachardoublequoteclose}\isanewline
   459 %
   463 %
   460 \endisadelimproof
   464 \isadelimproof
   461 %
   465 %
   462 \isatagproof
   466 \endisadelimproof
   463 \isamarkupfalse%
   467 %
   464 \isacommand{apply}{\isacharparenleft}split\ list{\isachardot}split{\isacharparenright}\isamarkuptrue%
   468 \isatagproof
   465 %
   469 \isacommand{apply}\isamarkupfalse%
       
   470 {\isacharparenleft}split\ list{\isachardot}split{\isacharparenright}%
   466 \begin{isamarkuptxt}%
   471 \begin{isamarkuptxt}%
   467 \begin{isabelle}%
   472 \begin{isabelle}%
   468 \ {\isadigit{1}}{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}\ {\isasymand}\isanewline
   473 \ {\isadigit{1}}{\isachardot}\ {\isacharparenleft}xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymlongrightarrow}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}\ {\isasymand}\isanewline
   469 \isaindent{\ {\isadigit{1}}{\isachardot}\ }{\isacharparenleft}{\isasymforall}a\ list{\isachardot}\ xs\ {\isacharequal}\ a\ {\isacharhash}\ list\ {\isasymlongrightarrow}\ a\ {\isacharhash}\ list\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}%
   474 \isaindent{\ {\isadigit{1}}{\isachardot}\ }{\isacharparenleft}{\isasymforall}a\ list{\isachardot}\ xs\ {\isacharequal}\ a\ {\isacharhash}\ list\ {\isasymlongrightarrow}\ a\ {\isacharhash}\ list\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ zs{\isacharparenright}%
   470 \end{isabelle}
   475 \end{isabelle}
   474 Instead, the simplifier has a modifier
   479 Instead, the simplifier has a modifier
   475 \isa{split}\index{*split (modifier)} 
   480 \isa{split}\index{*split (modifier)} 
   476 for adding splitting rules explicitly.  The
   481 for adding splitting rules explicitly.  The
   477 lemma above can be proved in one step by%
   482 lemma above can be proved in one step by%
   478 \end{isamarkuptxt}%
   483 \end{isamarkuptxt}%
   479 %
   484 \isamarkuptrue%
   480 \endisatagproof
   485 \isamarkupfalse%
   481 {\isafoldproof}%
   486 %
   482 %
   487 \endisatagproof
   483 \isadelimproof
   488 {\isafoldproof}%
   484 %
   489 %
   485 \endisadelimproof
   490 \isadelimproof
   486 %
   491 %
   487 \isadelimproof
   492 \endisadelimproof
   488 %
   493 \isamarkupfalse%
   489 \endisadelimproof
   494 %
   490 %
   495 \isadelimproof
   491 \isatagproof
   496 %
   492 \isamarkupfalse%
   497 \endisadelimproof
   493 \isacommand{apply}{\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}%
   498 %
   494 \endisatagproof
   499 \isatagproof
   495 {\isafoldproof}%
   500 \isacommand{apply}\isamarkupfalse%
   496 %
   501 {\isacharparenleft}simp\ split{\isacharcolon}\ list{\isachardot}split{\isacharparenright}\isamarkupfalse%
   497 \isadelimproof
   502 %
   498 %
   503 \endisatagproof
   499 \endisadelimproof
   504 {\isafoldproof}%
   500 \isamarkuptrue%
   505 %
       
   506 \isadelimproof
       
   507 %
       
   508 \endisadelimproof
   501 %
   509 %
   502 \begin{isamarkuptext}%
   510 \begin{isamarkuptext}%
   503 \noindent
   511 \noindent
   504 whereas \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not succeed.
   512 whereas \isacommand{apply}\isa{{\isacharparenleft}simp{\isacharparenright}} alone will not succeed.
   505 
   513 
   506 Every datatype $t$ comes with a theorem
   514 Every datatype $t$ comes with a theorem
   507 $t$\isa{{\isachardot}split} which can be declared to be a \bfindex{split rule} either
   515 $t$\isa{{\isachardot}split} which can be declared to be a \bfindex{split rule} either
   508 locally as above, or by giving it the \attrdx{split} attribute globally:%
   516 locally as above, or by giving it the \attrdx{split} attribute globally:%
   509 \end{isamarkuptext}%
   517 \end{isamarkuptext}%
   510 \isamarkupfalse%
   518 \isamarkuptrue%
   511 \isacommand{declare}\ list{\isachardot}split\ {\isacharbrackleft}split{\isacharbrackright}\isamarkuptrue%
   519 \isacommand{declare}\isamarkupfalse%
   512 %
   520 \ list{\isachardot}split\ {\isacharbrackleft}split{\isacharbrackright}%
   513 \begin{isamarkuptext}%
   521 \begin{isamarkuptext}%
   514 \noindent
   522 \noindent
   515 The \isa{split} attribute can be removed with the \isa{del} modifier,
   523 The \isa{split} attribute can be removed with the \isa{del} modifier,
   516 either locally%
   524 either locally%
   517 \end{isamarkuptext}%
   525 \end{isamarkuptext}%
   518 %
   526 \isamarkuptrue%
   519 \isadelimproof
   527 \isamarkupfalse%
   520 %
   528 %
   521 \endisadelimproof
   529 \isadelimproof
   522 %
   530 %
   523 \isatagproof
   531 \endisadelimproof
   524 \isamarkupfalse%
   532 %
   525 \isacommand{apply}{\isacharparenleft}simp\ split\ del{\isacharcolon}\ split{\isacharunderscore}if{\isacharparenright}%
   533 \isatagproof
   526 \endisatagproof
   534 \isacommand{apply}\isamarkupfalse%
   527 {\isafoldproof}%
   535 {\isacharparenleft}simp\ split\ del{\isacharcolon}\ split{\isacharunderscore}if{\isacharparenright}\isamarkupfalse%
   528 %
   536 %
   529 \isadelimproof
   537 \endisatagproof
   530 %
   538 {\isafoldproof}%
   531 \endisadelimproof
   539 %
   532 \isamarkuptrue%
   540 \isadelimproof
       
   541 %
       
   542 \endisadelimproof
   533 %
   543 %
   534 \begin{isamarkuptext}%
   544 \begin{isamarkuptext}%
   535 \noindent
   545 \noindent
   536 or globally:%
   546 or globally:%
   537 \end{isamarkuptext}%
   547 \end{isamarkuptext}%
   538 \isamarkupfalse%
   548 \isamarkuptrue%
   539 \isacommand{declare}\ list{\isachardot}split\ {\isacharbrackleft}split\ del{\isacharbrackright}\isamarkuptrue%
   549 \isacommand{declare}\isamarkupfalse%
   540 %
   550 \ list{\isachardot}split\ {\isacharbrackleft}split\ del{\isacharbrackright}%
   541 \begin{isamarkuptext}%
   551 \begin{isamarkuptext}%
   542 Polished proofs typically perform splitting within \isa{simp} rather than 
   552 Polished proofs typically perform splitting within \isa{simp} rather than 
   543 invoking the \isa{split} method.  However, if a goal contains
   553 invoking the \isa{split} method.  However, if a goal contains
   544 several \isa{if} and \isa{case} expressions, 
   554 several \isa{if} and \isa{case} expressions, 
   545 the \isa{split} method can be
   555 the \isa{split} method can be
   548 The split rules shown above are intended to affect only the subgoal's
   558 The split rules shown above are intended to affect only the subgoal's
   549 conclusion.  If you want to split an \isa{if} or \isa{case}-expression
   559 conclusion.  If you want to split an \isa{if} or \isa{case}-expression
   550 in the assumptions, you have to apply \tdx{split_if_asm} or
   560 in the assumptions, you have to apply \tdx{split_if_asm} or
   551 $t$\isa{{\isachardot}split{\isacharunderscore}asm}:%
   561 $t$\isa{{\isachardot}split{\isacharunderscore}asm}:%
   552 \end{isamarkuptext}%
   562 \end{isamarkuptext}%
   553 \isamarkupfalse%
   563 \isamarkuptrue%
   554 \isacommand{lemma}\ {\isachardoublequote}if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ else\ ys\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ xs\ {\isacharat}\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline
   564 \isacommand{lemma}\isamarkupfalse%
   555 %
   565 \ {\isachardoublequoteopen}if\ xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ then\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ else\ ys\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ xs\ {\isacharat}\ ys\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}\isanewline
   556 \isadelimproof
   566 %
   557 %
   567 \isadelimproof
   558 \endisadelimproof
   568 %
   559 %
   569 \endisadelimproof
   560 \isatagproof
   570 %
   561 \isamarkupfalse%
   571 \isatagproof
   562 \isacommand{apply}{\isacharparenleft}split\ split{\isacharunderscore}if{\isacharunderscore}asm{\isacharparenright}\isamarkuptrue%
   572 \isacommand{apply}\isamarkupfalse%
   563 %
   573 {\isacharparenleft}split\ split{\isacharunderscore}if{\isacharunderscore}asm{\isacharparenright}%
   564 \begin{isamarkuptxt}%
   574 \begin{isamarkuptxt}%
   565 \noindent
   575 \noindent
   566 Unlike splitting the conclusion, this step creates two
   576 Unlike splitting the conclusion, this step creates two
   567 separate subgoals, which here can be solved by \isa{simp{\isacharunderscore}all}:
   577 separate subgoals, which here can be solved by \isa{simp{\isacharunderscore}all}:
   568 \begin{isabelle}%
   578 \begin{isabelle}%
   581   same is true for \sdx{case}-expressions: only the selector is
   591   same is true for \sdx{case}-expressions: only the selector is
   582   simplified at first, until either the expression reduces to one of the
   592   simplified at first, until either the expression reduces to one of the
   583   cases or it is split.
   593   cases or it is split.
   584 \end{warn}%
   594 \end{warn}%
   585 \end{isamarkuptxt}%
   595 \end{isamarkuptxt}%
   586 %
   596 \isamarkuptrue%
   587 \endisatagproof
   597 \isamarkupfalse%
   588 {\isafoldproof}%
   598 %
   589 %
   599 \endisatagproof
   590 \isadelimproof
   600 {\isafoldproof}%
   591 %
   601 %
   592 \endisadelimproof
   602 \isadelimproof
   593 \isamarkuptrue%
   603 %
       
   604 \endisadelimproof
   594 %
   605 %
   595 \isamarkupsubsection{Tracing%
   606 \isamarkupsubsection{Tracing%
   596 }
   607 }
   597 \isamarkuptrue%
   608 \isamarkuptrue%
   598 %
   609 %
   599 \begin{isamarkuptext}%
   610 \begin{isamarkuptext}%
   600 \indexbold{tracing the simplifier}
   611 \indexbold{tracing the simplifier}
   601 Using the simplifier effectively may take a bit of experimentation.  Set the
   612 Using the simplifier effectively may take a bit of experimentation.  Set the
   602 Proof General flag \pgmenu{Isabelle} $>$ \pgmenu{Settings} $>$ \pgmenu{Trace Simplifier} to get a better idea of what is going on:%
   613 Proof General flag \pgmenu{Isabelle} $>$ \pgmenu{Settings} $>$ \pgmenu{Trace Simplifier} to get a better idea of what is going on:%
   603 \end{isamarkuptext}%
   614 \end{isamarkuptext}%
   604 \isamarkupfalse%
   615 \isamarkuptrue%
   605 \isacommand{lemma}\ {\isachardoublequote}rev\ {\isacharbrackleft}a{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline
   616 \isacommand{lemma}\isamarkupfalse%
   606 %
   617 \ {\isachardoublequoteopen}rev\ {\isacharbrackleft}a{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}\isanewline
   607 \isadelimproof
   618 %
   608 %
   619 \isadelimproof
   609 \endisadelimproof
   620 %
   610 %
   621 \endisadelimproof
   611 \isatagproof
   622 %
   612 \isamarkupfalse%
   623 \isatagproof
   613 \isacommand{apply}{\isacharparenleft}simp{\isacharparenright}%
   624 \isacommand{apply}\isamarkupfalse%
   614 \endisatagproof
   625 {\isacharparenleft}simp{\isacharparenright}\isamarkupfalse%
   615 {\isafoldproof}%
   626 %
   616 %
   627 \endisatagproof
   617 \isadelimproof
   628 {\isafoldproof}%
   618 %
   629 %
   619 \endisadelimproof
   630 \isadelimproof
   620 \isamarkuptrue%
   631 %
       
   632 \endisadelimproof
   621 %
   633 %
   622 \begin{isamarkuptext}%
   634 \begin{isamarkuptext}%
   623 \noindent
   635 \noindent
   624 produces the following trace in Proof General's \pgmenu{Trace} buffer:
   636 produces the following trace in Proof General's \pgmenu{Trace} buffer:
   625 
   637 
   751 If you click on \pgmenu{Find}, you can use the arrow keys to scroll
   763 If you click on \pgmenu{Find}, you can use the arrow keys to scroll
   752 through previous searches and just modify them. This saves you having
   764 through previous searches and just modify them. This saves you having
   753 to type in lengthy expressions again and again.
   765 to type in lengthy expressions again and again.
   754 \end{pgnote}%
   766 \end{pgnote}%
   755 \end{isamarkuptext}%
   767 \end{isamarkuptext}%
       
   768 \isamarkuptrue%
   756 %
   769 %
   757 \isadelimtheory
   770 \isadelimtheory
   758 %
   771 %
   759 \endisadelimtheory
   772 \endisadelimtheory
   760 %
   773 %
   761 \isatagtheory
   774 \isatagtheory
       
   775 \isamarkupfalse%
   762 %
   776 %
   763 \endisatagtheory
   777 \endisatagtheory
   764 {\isafoldtheory}%
   778 {\isafoldtheory}%
   765 %
   779 %
   766 \isadelimtheory
   780 \isadelimtheory