77 include @{prop"(x-y)-z = (x-z)-y"} in arithmetic and @{prop"insert x (insert |
77 include @{prop"(x-y)-z = (x-z)-y"} in arithmetic and @{prop"insert x (insert |
78 y A) = insert y (insert x A)"} for sets. Such rules are problematic because |
78 y A) = insert y (insert x A)"} for sets. Such rules are problematic because |
79 once they apply, they can be used forever. The simplifier is aware of this |
79 once they apply, they can be used forever. The simplifier is aware of this |
80 danger and treats permutative rules by means of a special strategy, called |
80 danger and treats permutative rules by means of a special strategy, called |
81 \bfindex{ordered rewriting}: a permutative rewrite |
81 \bfindex{ordered rewriting}: a permutative rewrite |
82 rule is only applied if the term becomes ``smaller'' (with respect to a fixed |
82 rule is only applied if the term becomes smaller with respect to a fixed |
83 lexicographic ordering on terms). For example, commutativity rewrites |
83 lexicographic ordering on terms. For example, commutativity rewrites |
84 @{term"b+a"} to @{term"a+b"}, but then stops because @{term"a+b"} is strictly |
84 @{term"b+a"} to @{term"a+b"}, but then stops because @{term"a+b"} is strictly |
85 smaller than @{term"b+a"}. Permutative rewrite rules can be turned into |
85 smaller than @{term"b+a"}. Permutative rewrite rules can be turned into |
86 simplification rules in the usual manner via the @{text simp} attribute; the |
86 simplification rules in the usual manner via the @{text simp} attribute; the |
87 simplifier recognizes their special status automatically. |
87 simplifier recognizes their special status automatically. |
88 |
88 |
129 pattern}\indexbold{pattern, higher-order}. This restricts where |
129 pattern}\indexbold{pattern, higher-order}. This restricts where |
130 unknowns may occur. Higher-order patterns are terms in $\beta$-normal |
130 unknowns may occur. Higher-order patterns are terms in $\beta$-normal |
131 form (this will always be the case unless you have done something |
131 form (this will always be the case unless you have done something |
132 strange) where each occurrence of an unknown is of the form |
132 strange) where each occurrence of an unknown is of the form |
133 $\Var{f}~x@1~\dots~x@n$, where the $x@i$ are distinct bound |
133 $\Var{f}~x@1~\dots~x@n$, where the $x@i$ are distinct bound |
134 variables. Thus all ``standard'' rewrite rules, where all unknowns are |
134 variables. Thus all ordinary rewrite rules, where all unknowns are |
135 of base type, for example @{thm add_assoc}, are OK: if an unknown is |
135 of base type, for example @{thm add_assoc}, are OK: if an unknown is |
136 of base type, it cannot have any arguments. Additionally, the rule |
136 of base type, it cannot have any arguments. Additionally, the rule |
137 @{text"(\<forall>x. ?P x \<and> ?Q x) = ((\<forall>x. ?P x) \<and> (\<forall>x. ?Q x))"} is also OK, in |
137 @{text"(\<forall>x. ?P x \<and> ?Q x) = ((\<forall>x. ?P x) \<and> (\<forall>x. ?Q x))"} is also OK, in |
138 both directions: all arguments of the unknowns @{text"?P"} and |
138 both directions: all arguments of the unknowns @{text"?P"} and |
139 @{text"?Q"} are distinct bound variables. |
139 @{text"?Q"} are distinct bound variables. |