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 |