author wenzelm Sun, 04 Nov 2012 19:05:34 +0100 changeset 50064 e08cc8b20564 parent 50063 7e491da6bcbd child 50065 7c01dc2dcb8c
refurbished Simplifier examples;
 src/Doc/IsarRef/Generic.thy file | annotate | diff | comparison | revisions src/Doc/Ref/document/simplifier.tex file | annotate | diff | comparison | revisions
--- a/src/Doc/IsarRef/Generic.thy	Sat Nov 03 21:31:40 2012 +0100
+++ b/src/Doc/IsarRef/Generic.thy	Sun Nov 04 19:05:34 2012 +0100
@@ -496,6 +496,7 @@
\end{tabular}
\end{center}

+  %FIXME move?
\medskip The Splitter package is usually configured to work as part
of the Simplifier.  The effect of repeatedly applying @{ML
split_tac} can be simulated by @{text "(simp only: split:
@@ -504,6 +505,95 @@
*}

+subsubsection {* Examples *}
+
+text {* We consider basic algebraic simplifications in Isabelle/HOL.
+  The rather trivial goal @{prop "0 + (x + 0) = x + 0 + 0"} looks like
+  a good candidate to be solved by a single call of @{method simp}:
+*}
+
+lemma "0 + (x + 0) = x + 0 + 0" apply simp? oops
+
+text {* The above attempt \emph{fails}, because @{term "0"} and @{term
+  "op +"} in the HOL library are declared as generic type class
+  operations, without stating any algebraic laws yet.  More specific
+  of the theory context, e.g.\ like this: *}
+
+lemma fixes x :: nat shows "0 + (x + 0) = x + 0 + 0" by simp
+lemma fixes x :: int shows "0 + (x + 0) = x + 0 + 0" by simp
+lemma fixes x :: "'a :: monoid_add" shows "0 + (x + 0) = x + 0 + 0" by simp
+
+text {*
+  \medskip In many cases, assumptions of a subgoal are also needed in
+  the simplification process.  For example:
+*}
+
+lemma fixes x :: nat shows "x = 0 \<Longrightarrow> x + x = 0" by simp
+lemma fixes x :: nat assumes "x = 0" shows "x + x = 0" apply simp oops
+lemma fixes x :: nat assumes "x = 0" shows "x + x = 0" using assms by simp
+
+text {* As seen above, local assumptions that shall contribute to
+  simplification need to be part of the subgoal already, or indicated
+  explicitly for use by the subsequent method invocation.  Both too
+  little or too much information can make simplification fail, for
+  different reasons.
+
+  In the next example the malicious assumption @{prop "\<And>x::nat. f x =
+  g (f (g x))"} does not contribute to solve the problem, but makes
+  the default @{method simp} method loop: the rewrite rule @{text "f
+  ?x \<equiv> g (f (g ?x))"} extracted from the assumption does not
+  terminate.  The Simplifier notices certain simple forms of
+  nontermination, but not this one.  The problem can be solved
+  nonetheless, by ignoring assumptions via special options as
+  explained before:
+*}
+
+lemma "(\<And>x::nat. f x = g (f (g x))) \<Longrightarrow> f 0 = f 0 + 0"
+  by (simp (no_asm))
+
+text {* The latter form is typical for long unstructured proof
+  scripts, where the control over the goal content is limited.  In
+  structured proofs it is usually better to avoid pushing too many
+  facts into the goal state in the first place.  Assumptions in the
+  Isar proof context do not intrude the reasoning if not used
+  explicitly.  This is illustrated for a toplevel statement and a
+  local proof body as follows:
+*}
+
+lemma
+  assumes "\<And>x::nat. f x = g (f (g x))"
+  shows "f 0 = f 0 + 0" by simp
+
+begin
+  assume "\<And>x::nat. f x = g (f (g x))"
+  have "f 0 = f 0 + 0" by simp
+end
+
+text {* \medskip Because assumptions may simplify each other, there
+  can be very subtle cases of nontermination. For example, the regular
+  @{method simp} method applied to @{prop "P (f x) \<Longrightarrow> y = x \<Longrightarrow> f x = f y
+  \<Longrightarrow> Q"} gives rise to the infinite reduction sequence
+  $+ @{text "P (f x)"} \stackrel{@{text "f x \<equiv> f y"}}{\longmapsto} + @{text "P (f y)"} \stackrel{@{text "y \<equiv> x"}}{\longmapsto} + @{text "P (f x)"} \stackrel{@{text "f x \<equiv> f y"}}{\longmapsto} \cdots +$
+  whereas applying the same to @{prop "y = x \<Longrightarrow> f x = f y \<Longrightarrow> P (f x) \<Longrightarrow>
+  Q"} terminates (without solving the goal):
+*}
+
+lemma "y = x \<Longrightarrow> f x = f y \<Longrightarrow> P (f x) \<Longrightarrow> Q"
+  apply simp
+  oops
+
+  Simplifier trace mode, which often helps to diagnose problems with
+  rewrite systems.
+*}
+
+
subsection {* Declaring rules \label{sec:simp-rules} *}

text {*
--- a/src/Doc/Ref/document/simplifier.tex	Sat Nov 03 21:31:40 2012 +0100
+++ b/src/Doc/Ref/document/simplifier.tex	Sun Nov 04 19:05:34 2012 +0100
@@ -7,90 +7,6 @@
\section{Simplification for dummies}
\label{sec:simp-for-dummies}

-\subsection{Simplification tactics} \label{sec:simp-for-dummies-tacs}
-\begin{ttbox}
-Simp_tac          : int -> tactic
-Asm_simp_tac      : int -> tactic
-Full_simp_tac     : int -> tactic
-Asm_full_simp_tac : int -> tactic
-\end{ttbox}
-
-\begin{ttdescription}
-\item[\ttindexbold{Simp_tac} $i$] simplifies subgoal~$i$ using the
-  current simpset.  It may solve the subgoal completely if it has
-  become trivial, using the simpset's solver tactic.
-
-\item[\ttindexbold{Asm_simp_tac}]\index{assumptions!in simplification}
-  is like \verb$Simp_tac$, but extracts additional rewrite rules from
-  the local assumptions.
-
-\item[\ttindexbold{Full_simp_tac}] is like \verb$Simp_tac$, but also
-  simplifies the assumptions (without using the assumptions to
-  simplify each other or the actual goal).
-
-\item[\ttindexbold{Asm_full_simp_tac}] is like \verb$Asm_simp_tac$,
-  but also simplifies the assumptions. In particular, assumptions can
-  simplify each other.
-\footnote{\texttt{Asm_full_simp_tac} used to process the assumptions from
-  left to right. For backwards compatibilty reasons only there is now
-  \texttt{Asm_lr_simp_tac} that behaves like the old \texttt{Asm_full_simp_tac}.}
-\end{ttdescription}
-
-\medskip
-
-As an example, consider the theory of arithmetic in HOL.  The (rather trivial)
-goal $0 + (x + 0) = x + 0 + 0$ can be solved by a single call of
-\texttt{Simp_tac} as follows:
-\begin{ttbox}
-context Arith.thy;
-Goal "0 + (x + 0) = x + 0 + 0";
-{\out  1. 0 + (x + 0) = x + 0 + 0}
-by (Simp_tac 1);
-{\out Level 1}
-{\out 0 + (x + 0) = x + 0 + 0}
-{\out No subgoals!}
-\end{ttbox}
-
-The simplifier uses the current simpset of \texttt{Arith.thy}, which
-contains suitable theorems like $\Var{n}+0 = \Var{n}$ and $0+\Var{n} = -\Var{n}$.
-
-\medskip In many cases, assumptions of a subgoal are also needed in
-the simplification process.  For example, \texttt{x = 0 ==> x + x = 0}
-is solved by \texttt{Asm_simp_tac} as follows:
-\begin{ttbox}
-{\out  1. x = 0 ==> x + x = 0}
-by (Asm_simp_tac 1);
-\end{ttbox}
-
-\medskip \texttt{Asm_full_simp_tac} is the most powerful of this quartet
-of tactics but may also loop where some of the others terminate.  For
-example,
-\begin{ttbox}
-{\out  1. ALL x. f x = g (f (g x)) ==> f 0 = f 0 + 0}
-\end{ttbox}
-is solved by \texttt{Simp_tac}, but \texttt{Asm_simp_tac} and {\tt
-  Asm_full_simp_tac} loop because the rewrite rule $f\,\Var{x} = -g\,(f\,(g\,\Var{x}))$ extracted from the assumption does not
-terminate.  Isabelle notices certain simple forms of nontermination,
-but not this one. Because assumptions may simplify each other, there can be
-very subtle cases of nontermination. For example, invoking
-{\tt Asm_full_simp_tac} on
-\begin{ttbox}
-{\out  1. [| P (f x); y = x; f x = f y |] ==> Q}
-\end{ttbox}
-gives rise to the infinite reduction sequence
-$-P\,(f\,x) \stackrel{f\,x = f\,y}{\longmapsto} P\,(f\,y) \stackrel{y = x}{\longmapsto} -P\,(f\,x) \stackrel{f\,x = f\,y}{\longmapsto} \cdots -$
-whereas applying the same tactic to
-\begin{ttbox}
-{\out  1. [| y = x; f x = f y; P (f x) |] ==> Q}
-\end{ttbox}
-terminates.
-
-
\subsection{Modifying the current simpset}
\begin{ttbox}
Addsimps    : thm list -> unit