doc-src/TutorialI/Recdef/document/simplification.tex
changeset 21261 58223c67fd8b
parent 17187 45bee2f6e61f
equal deleted inserted replaced
21260:11ba04d15f36 21261:58223c67fd8b
    45 something else that leads to the same problem: it splits 
    45 something else that leads to the same problem: it splits 
    46 each \isa{if}-expression unless its
    46 each \isa{if}-expression unless its
    47 condition simplifies to \isa{True} or \isa{False}.  For
    47 condition simplifies to \isa{True} or \isa{False}.  For
    48 example, simplification reduces
    48 example, simplification reduces
    49 \begin{isabelle}%
    49 \begin{isabelle}%
    50 \ \ \ \ \ simplification{\isachardot}gcd\ {\isacharparenleft}m{\isacharcomma}\ n{\isacharparenright}\ {\isacharequal}\ k%
    50 \ \ \ \ \ gcd\ {\isacharparenleft}m{\isacharcomma}\ n{\isacharparenright}\ {\isacharequal}\ k%
    51 \end{isabelle}
    51 \end{isabelle}
    52 in one step to
    52 in one step to
    53 \begin{isabelle}%
    53 \begin{isabelle}%
    54 \ \ \ \ \ {\isacharparenleft}if\ n\ {\isacharequal}\ {\isadigit{0}}\ then\ m\ else\ simplification{\isachardot}gcd\ {\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ k%
    54 \ \ \ \ \ {\isacharparenleft}if\ n\ {\isacharequal}\ {\isadigit{0}}\ then\ m\ else\ gcd\ {\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}{\isacharparenright}\ {\isacharequal}\ k%
    55 \end{isabelle}
    55 \end{isabelle}
    56 where the condition cannot be reduced further, and splitting leads to
    56 where the condition cannot be reduced further, and splitting leads to
    57 \begin{isabelle}%
    57 \begin{isabelle}%
    58 \ \ \ \ \ {\isacharparenleft}n\ {\isacharequal}\ {\isadigit{0}}\ {\isasymlongrightarrow}\ m\ {\isacharequal}\ k{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}n\ {\isasymnoteq}\ {\isadigit{0}}\ {\isasymlongrightarrow}\ simplification{\isachardot}gcd\ {\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}\ {\isacharequal}\ k{\isacharparenright}%
    58 \ \ \ \ \ {\isacharparenleft}n\ {\isacharequal}\ {\isadigit{0}}\ {\isasymlongrightarrow}\ m\ {\isacharequal}\ k{\isacharparenright}\ {\isasymand}\ {\isacharparenleft}n\ {\isasymnoteq}\ {\isadigit{0}}\ {\isasymlongrightarrow}\ gcd\ {\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}\ {\isacharequal}\ k{\isacharparenright}%
    59 \end{isabelle}
    59 \end{isabelle}
    60 Since the recursive call \isa{simplification{\isachardot}gcd\ {\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}} is no longer protected by
    60 Since the recursive call \isa{gcd\ {\isacharparenleft}n{\isacharcomma}\ m\ mod\ n{\isacharparenright}} is no longer protected by
    61 an \isa{if}, it is unfolded again, which leads to an infinite chain of
    61 an \isa{if}, it is unfolded again, which leads to an infinite chain of
    62 simplification steps. Fortunately, this problem can be avoided in many
    62 simplification steps. Fortunately, this problem can be avoided in many
    63 different ways.
    63 different ways.
    64 
    64 
    65 The most radical solution is to disable the offending theorem
    65 The most radical solution is to disable the offending theorem
    67 as shown in \S\ref{sec:AutoCaseSplits}.  However, we do not recommend this
    67 as shown in \S\ref{sec:AutoCaseSplits}.  However, we do not recommend this
    68 approach: you will often have to invoke the rule explicitly when
    68 approach: you will often have to invoke the rule explicitly when
    69 \isa{if} is involved.
    69 \isa{if} is involved.
    70 
    70 
    71 If possible, the definition should be given by pattern matching on the left
    71 If possible, the definition should be given by pattern matching on the left
    72 rather than \isa{if} on the right. In the case of \isa{simplification{\isachardot}gcd} the
    72 rather than \isa{if} on the right. In the case of \isa{gcd} the
    73 following alternative definition suggests itself:%
    73 following alternative definition suggests itself:%
    74 \end{isamarkuptext}%
    74 \end{isamarkuptext}%
    75 \isamarkuptrue%
    75 \isamarkuptrue%
    76 \isacommand{consts}\isamarkupfalse%
    76 \isacommand{consts}\isamarkupfalse%
    77 \ gcd{\isadigit{1}}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}nat{\isasymtimes}nat\ {\isasymRightarrow}\ nat{\isachardoublequoteclose}\isanewline
    77 \ gcd{\isadigit{1}}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}nat{\isasymtimes}nat\ {\isasymRightarrow}\ nat{\isachardoublequoteclose}\isanewline
    98 \noindent
    98 \noindent
    99 This is probably the neatest solution next to pattern matching, and it is
    99 This is probably the neatest solution next to pattern matching, and it is
   100 always available.
   100 always available.
   101 
   101 
   102 A final alternative is to replace the offending simplification rules by
   102 A final alternative is to replace the offending simplification rules by
   103 derived conditional ones. For \isa{simplification{\isachardot}gcd} it means we have to prove
   103 derived conditional ones. For \isa{gcd} it means we have to prove
   104 these lemmas:%
   104 these lemmas:%
   105 \end{isamarkuptext}%
   105 \end{isamarkuptext}%
   106 \isamarkuptrue%
   106 \isamarkuptrue%
   107 \isacommand{lemma}\isamarkupfalse%
   107 \isacommand{lemma}\isamarkupfalse%
   108 \ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequoteopen}gcd\ {\isacharparenleft}m{\isacharcomma}\ {\isadigit{0}}{\isacharparenright}\ {\isacharequal}\ m{\isachardoublequoteclose}\isanewline
   108 \ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequoteopen}gcd\ {\isacharparenleft}m{\isacharcomma}\ {\isadigit{0}}{\isacharparenright}\ {\isacharequal}\ m{\isachardoublequoteclose}\isanewline