21 contextual information can also be made available for other |
21 contextual information can also be made available for other |
22 operators. For example, @{prop"xs = [] --> xs@xs = xs"} simplifies to @{term |
22 operators. For example, @{prop"xs = [] --> xs@xs = xs"} simplifies to @{term |
23 True} because we may use @{prop"xs = []"} when simplifying @{prop"xs@xs = |
23 True} because we may use @{prop"xs = []"} when simplifying @{prop"xs@xs = |
24 xs"}. The generation of contextual information during simplification is |
24 xs"}. The generation of contextual information during simplification is |
25 controlled by so-called \bfindex{congruence rules}. This is the one for |
25 controlled by so-called \bfindex{congruence rules}. This is the one for |
26 @{text"\<longrightarrow>"}: |
26 \<open>\<longrightarrow>\<close>: |
27 @{thm[display]imp_cong[no_vars]} |
27 @{thm[display]imp_cong[no_vars]} |
28 It should be read as follows: |
28 It should be read as follows: |
29 In order to simplify @{prop"P-->Q"} to @{prop"P'-->Q'"}, |
29 In order to simplify @{prop"P-->Q"} to @{prop"P'-->Q'"}, |
30 simplify @{prop P} to @{prop P'} |
30 simplify @{prop P} to @{prop P'} |
31 and assume @{prop"P'"} when simplifying @{prop Q} to @{prop"Q'"}. |
31 and assume @{prop"P'"} when simplifying @{prop Q} to @{prop"Q'"}. |
32 |
32 |
33 Here are some more examples. The congruence rules for bounded |
33 Here are some more examples. The congruence rules for bounded |
34 quantifiers supply contextual information about the bound variable: |
34 quantifiers supply contextual information about the bound variable: |
35 @{thm[display,eta_contract=false,margin=60]ball_cong[no_vars]} |
35 @{thm[display,eta_contract=false,margin=60]ball_cong[no_vars]} |
36 One congruence rule for conditional expressions supplies contextual |
36 One congruence rule for conditional expressions supplies contextual |
37 information for simplifying the @{text then} and @{text else} cases: |
37 information for simplifying the \<open>then\<close> and \<open>else\<close> cases: |
38 @{thm[display]if_cong[no_vars]} |
38 @{thm[display]if_cong[no_vars]} |
39 An alternative congruence rule for conditional expressions |
39 An alternative congruence rule for conditional expressions |
40 actually \emph{prevents} simplification of some arguments: |
40 actually \emph{prevents} simplification of some arguments: |
41 @{thm[display]if_weak_cong[no_vars]} |
41 @{thm[display]if_weak_cong[no_vars]} |
42 Only the first argument is simplified; the others remain unchanged. |
42 Only the first argument is simplified; the others remain unchanged. |
43 This makes simplification much faster and is faithful to the evaluation |
43 This makes simplification much faster and is faithful to the evaluation |
44 strategy in programming languages, which is why this is the default |
44 strategy in programming languages, which is why this is the default |
45 congruence rule for @{text "if"}. Analogous rules control the evaluation of |
45 congruence rule for \<open>if\<close>. Analogous rules control the evaluation of |
46 @{text case} expressions. |
46 \<open>case\<close> expressions. |
47 |
47 |
48 You can declare your own congruence rules with the attribute \attrdx{cong}, |
48 You can declare your own congruence rules with the attribute \attrdx{cong}, |
49 either globally, in the usual manner, |
49 either globally, in the usual manner, |
50 \begin{quote} |
50 \begin{quote} |
51 \isacommand{declare} \textit{theorem-name} @{text"[cong]"} |
51 \isacommand{declare} \textit{theorem-name} \<open>[cong]\<close> |
52 \end{quote} |
52 \end{quote} |
53 or locally in a @{text"simp"} call by adding the modifier |
53 or locally in a \<open>simp\<close> call by adding the modifier |
54 \begin{quote} |
54 \begin{quote} |
55 @{text"cong:"} \textit{list of theorem names} |
55 \<open>cong:\<close> \textit{list of theorem names} |
56 \end{quote} |
56 \end{quote} |
57 The effect is reversed by @{text"cong del"} instead of @{text cong}. |
57 The effect is reversed by \<open>cong del\<close> instead of \<open>cong\<close>. |
58 |
58 |
59 \begin{warn} |
59 \begin{warn} |
60 The congruence rule @{thm[source]conj_cong} |
60 The congruence rule @{thm[source]conj_cong} |
61 @{thm[display]conj_cong[no_vars]} |
61 @{thm[display]conj_cong[no_vars]} |
62 \par\noindent |
62 \par\noindent |
78 \bfindex{ordered rewriting}: a permutative rewrite |
78 \bfindex{ordered rewriting}: a permutative rewrite |
79 rule is only applied if the term becomes smaller with respect to a fixed |
79 rule is only applied if the term becomes smaller with respect to a fixed |
80 lexicographic ordering on terms. For example, commutativity rewrites |
80 lexicographic ordering on terms. For example, commutativity rewrites |
81 @{term"b+a"} to @{term"a+b"}, but then stops because @{term"a+b"} is strictly |
81 @{term"b+a"} to @{term"a+b"}, but then stops because @{term"a+b"} is strictly |
82 smaller than @{term"b+a"}. Permutative rewrite rules can be turned into |
82 smaller than @{term"b+a"}. Permutative rewrite rules can be turned into |
83 simplification rules in the usual manner via the @{text simp} attribute; the |
83 simplification rules in the usual manner via the \<open>simp\<close> attribute; the |
84 simplifier recognizes their special status automatically. |
84 simplifier recognizes their special status automatically. |
85 |
85 |
86 Permutative rewrite rules are most effective in the case of |
86 Permutative rewrite rules are most effective in the case of |
87 associative-commutative functions. (Associativity by itself is not |
87 associative-commutative functions. (Associativity by itself is not |
88 permutative.) When dealing with an AC-function~$f$, keep the |
88 permutative.) When dealing with an AC-function~$f$, keep the |
100 Ordered rewriting with the combination of A, C, and LC sorts a term |
100 Ordered rewriting with the combination of A, C, and LC sorts a term |
101 lexicographically: |
101 lexicographically: |
102 \[\def\maps#1{~\stackrel{#1}{\leadsto}~} |
102 \[\def\maps#1{~\stackrel{#1}{\leadsto}~} |
103 f(f(b,c),a) \maps{A} f(b,f(c,a)) \maps{C} f(b,f(a,c)) \maps{LC} f(a,f(b,c)) \] |
103 f(f(b,c),a) \maps{A} f(b,f(c,a)) \maps{C} f(b,f(a,c)) \maps{LC} f(a,f(b,c)) \] |
104 |
104 |
105 Note that ordered rewriting for @{text"+"} and @{text"*"} on numbers is rarely |
105 Note that ordered rewriting for \<open>+\<close> and \<open>*\<close> on numbers is rarely |
106 necessary because the built-in arithmetic prover often succeeds without |
106 necessary because the built-in arithmetic prover often succeeds without |
107 such tricks. |
107 such tricks. |
108 \<close> |
108 \<close> |
109 |
109 |
110 subsection\<open>How the Simplifier Works\<close> |
110 subsection\<open>How the Simplifier Works\<close> |
130 Each occurrence of an unknown is of the form |
130 Each occurrence of an unknown is of the form |
131 $\Var{f}~x@1~\dots~x@n$, where the $x@i$ are distinct bound |
131 $\Var{f}~x@1~\dots~x@n$, where the $x@i$ are distinct bound |
132 variables. Thus all ordinary rewrite rules, where all unknowns are |
132 variables. Thus all ordinary rewrite rules, where all unknowns are |
133 of base type, for example @{thm add.assoc}, are acceptable: if an unknown is |
133 of base type, for example @{thm add.assoc}, are acceptable: if an unknown is |
134 of base type, it cannot have any arguments. Additionally, the rule |
134 of base type, it cannot have any arguments. Additionally, the rule |
135 @{text"(\<forall>x. ?P x \<and> ?Q x) = ((\<forall>x. ?P x) \<and> (\<forall>x. ?Q x))"} is also acceptable, in |
135 \<open>(\<forall>x. ?P x \<and> ?Q x) = ((\<forall>x. ?P x) \<and> (\<forall>x. ?Q x))\<close> is also acceptable, in |
136 both directions: all arguments of the unknowns @{text"?P"} and |
136 both directions: all arguments of the unknowns \<open>?P\<close> and |
137 @{text"?Q"} are distinct bound variables. |
137 \<open>?Q\<close> are distinct bound variables. |
138 |
138 |
139 If the left-hand side is not a higher-order pattern, all is not lost. |
139 If the left-hand side is not a higher-order pattern, all is not lost. |
140 The simplifier will still try to apply the rule provided it |
140 The simplifier will still try to apply the rule provided it |
141 matches directly: without much $\lambda$-calculus hocus |
141 matches directly: without much $\lambda$-calculus hocus |
142 pocus. For example, @{text"(?f ?x \<in> range ?f) = True"} rewrites |
142 pocus. For example, \<open>(?f ?x \<in> range ?f) = True\<close> rewrites |
143 @{term"g a \<in> range g"} to @{const True}, but will fail to match |
143 @{term"g a \<in> range g"} to @{const True}, but will fail to match |
144 @{text"g(h b) \<in> range(\<lambda>x. g(h x))"}. However, you can |
144 \<open>g(h b) \<in> range(\<lambda>x. g(h x))\<close>. However, you can |
145 eliminate the offending subterms --- those that are not patterns --- |
145 eliminate the offending subterms --- those that are not patterns --- |
146 by adding new variables and conditions. |
146 by adding new variables and conditions. |
147 In our example, we eliminate @{text"?f ?x"} and obtain |
147 In our example, we eliminate \<open>?f ?x\<close> and obtain |
148 @{text"?y = |
148 \<open>?y = |
149 ?f ?x \<Longrightarrow> (?y \<in> range ?f) = True"}, which is fine |
149 ?f ?x \<Longrightarrow> (?y \<in> range ?f) = True\<close>, which is fine |
150 as a conditional rewrite rule since conditions can be arbitrary |
150 as a conditional rewrite rule since conditions can be arbitrary |
151 terms. However, this trick is not a panacea because the newly |
151 terms. However, this trick is not a panacea because the newly |
152 introduced conditions may be hard to solve. |
152 introduced conditions may be hard to solve. |
153 |
153 |
154 There is no restriction on the form of the right-hand |
154 There is no restriction on the form of the right-hand |
168 \neg P &\mapsto& P = \hbox{\isa{False}} \nonumber\\ |
168 \neg P &\mapsto& P = \hbox{\isa{False}} \nonumber\\ |
169 P \longrightarrow Q &\mapsto& P \Longrightarrow Q \nonumber\\ |
169 P \longrightarrow Q &\mapsto& P \Longrightarrow Q \nonumber\\ |
170 P \land Q &\mapsto& P,\ Q \nonumber\\ |
170 P \land Q &\mapsto& P,\ Q \nonumber\\ |
171 \forall x.~P~x &\mapsto& P~\Var{x}\nonumber\\ |
171 \forall x.~P~x &\mapsto& P~\Var{x}\nonumber\\ |
172 \forall x \in A.\ P~x &\mapsto& \Var{x} \in A \Longrightarrow P~\Var{x} \nonumber\\ |
172 \forall x \in A.\ P~x &\mapsto& \Var{x} \in A \Longrightarrow P~\Var{x} \nonumber\\ |
173 @{text "if"}\ P\ @{text then}\ Q\ @{text else}\ R &\mapsto& |
173 \<open>if\<close>\ P\ \<open>then\<close>\ Q\ \<open>else\<close>\ R &\mapsto& |
174 P \Longrightarrow Q,\ \neg P \Longrightarrow R \nonumber |
174 P \Longrightarrow Q,\ \neg P \Longrightarrow R \nonumber |
175 \end{eqnarray} |
175 \end{eqnarray} |
176 Once this conversion process is finished, all remaining non-equations |
176 Once this conversion process is finished, all remaining non-equations |
177 $P$ are turned into trivial equations $P =\isa{True}$. |
177 $P$ are turned into trivial equations $P =\isa{True}$. |
178 For example, the formula |
178 For example, the formula |