src/Doc/Tutorial/Advanced/simp2.thy
changeset 69505 cc2d676d5395
parent 67406 23307fd33906
child 69597 ff784d5a5bfb
equal deleted inserted replaced
69504:bda7527ccf05 69505:cc2d676d5395
    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