--- a/doc-src/TutorialI/Misc/document/Itrev.tex Thu Jul 26 18:23:38 2001 +0200
+++ b/doc-src/TutorialI/Misc/document/Itrev.tex Fri Aug 03 18:04:55 2001 +0200
@@ -7,6 +7,7 @@
%
\begin{isamarkuptext}%
\label{sec:InductionHeuristics}
+\index{induction heuristics|(}%
The purpose of this section is to illustrate some simple heuristics for
inductive proofs. The first one we have already mentioned in our initial
example:
@@ -18,23 +19,29 @@
\emph{Do induction on argument number $i$ if the function is defined by
recursion in argument number $i$.}
\end{quote}
-When we look at the proof of \isa{{\isachardoublequote}{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ {\isacharparenleft}ys\ {\isacharat}\ zs{\isacharparenright}{\isachardoublequote}}
-in \S\ref{sec:intro-proof} we find (a) \isa{{\isacharat}} is recursive in
-the first argument, (b) \isa{xs} occurs only as the first argument of
-\isa{{\isacharat}}, and (c) both \isa{ys} and \isa{zs} occur at least once as
-the second argument of \isa{{\isacharat}}. Hence it is natural to perform induction
-on \isa{xs}.
+When we look at the proof of \isa{{\isacharparenleft}xs{\isacharat}ys{\isacharparenright}\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ {\isacharparenleft}ys{\isacharat}zs{\isacharparenright}}
+in \S\ref{sec:intro-proof} we find
+\begin{itemize}
+\item \isa{{\isacharat}} is recursive in
+the first argument
+\item \isa{xs} occurs only as the first argument of
+\isa{{\isacharat}}
+\item both \isa{ys} and \isa{zs} occur at least once as
+the second argument of \isa{{\isacharat}}
+\end{itemize}
+Hence it is natural to perform induction on~\isa{xs}.
The key heuristic, and the main point of this section, is to
-generalize the goal before induction. The reason is simple: if the goal is
+\emph{generalize the goal before induction}.
+The reason is simple: if the goal is
too specific, the induction hypothesis is too weak to allow the induction
step to go through. Let us illustrate the idea with an example.
-Function \isa{rev} has quadratic worst-case running time
+Function \cdx{rev} has quadratic worst-case running time
because it calls function \isa{{\isacharat}} for each element of the list and
\isa{{\isacharat}} is linear in its first argument. A linear time version of
\isa{rev} reqires an extra argument where the result is accumulated
-gradually, using only \isa{{\isacharhash}}:%
+gradually, using only~\isa{{\isacharhash}}:%
\end{isamarkuptext}%
\isacommand{consts}\ itrev\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\isanewline
\isacommand{primrec}\isanewline
@@ -42,10 +49,10 @@
{\isachardoublequote}itrev\ {\isacharparenleft}x{\isacharhash}xs{\isacharparenright}\ ys\ {\isacharequal}\ itrev\ xs\ {\isacharparenleft}x{\isacharhash}ys{\isacharparenright}{\isachardoublequote}%
\begin{isamarkuptext}%
\noindent
-The behaviour of \isa{itrev} is simple: it reverses
+The behaviour of \cdx{itrev} is simple: it reverses
its first argument by stacking its elements onto the second argument,
and returning that second argument when the first one becomes
-empty. Note that \isa{itrev} is tail-recursive, i.e.\ it can be
+empty. Note that \isa{itrev} is tail-recursive: it can be
compiled into a loop.
Naturally, we would like to show that \isa{itrev} does indeed reverse
@@ -59,32 +66,32 @@
\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharcomma}\ simp{\isacharunderscore}all{\isacharparenright}%
\begin{isamarkuptxt}%
\noindent
-Unfortunately, this is not a complete success:
+Unfortunately, this attempt does not prove
+the induction step:
\begin{isabelle}%
\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}a\ list{\isachardot}\isanewline
\isaindent{\ {\isadigit{1}}{\isachardot}\ \ \ \ }itrev\ list\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ rev\ list\ {\isasymLongrightarrow}\ itrev\ list\ {\isacharbrackleft}a{\isacharbrackright}\ {\isacharequal}\ rev\ list\ {\isacharat}\ {\isacharbrackleft}a{\isacharbrackright}%
\end{isabelle}
-Just as predicted above, the overall goal, and hence the induction
-hypothesis, is too weak to solve the induction step because of the fixed
-argument, \isa{{\isacharbrackleft}{\isacharbrackright}}. This suggests a heuristic:
-\begin{quote}
+The induction hypothesis is too weak. The fixed
+argument,~\isa{{\isacharbrackleft}{\isacharbrackright}}, prevents it from rewriting the conclusion.
+This example suggests a heuristic:
+\begin{quote}\index{generalizing induction formulae}%
\emph{Generalize goals for induction by replacing constants by variables.}
\end{quote}
Of course one cannot do this na\"{\i}vely: \isa{itrev\ xs\ ys\ {\isacharequal}\ rev\ xs} is
-just not true --- the correct generalization is%
+just not true. The correct generalization is%
\end{isamarkuptxt}%
\isacommand{lemma}\ {\isachardoublequote}itrev\ xs\ ys\ {\isacharequal}\ rev\ xs\ {\isacharat}\ ys{\isachardoublequote}%
\begin{isamarkuptxt}%
\noindent
If \isa{ys} is replaced by \isa{{\isacharbrackleft}{\isacharbrackright}}, the right-hand side simplifies to
-\isa{rev\ xs}, just as required.
+\isa{rev\ xs}, as required.
-In this particular instance it was easy to guess the right generalization,
-but in more complex situations a good deal of creativity is needed. This is
-the main source of complications in inductive proofs.
+In this instance it was easy to guess the right generalization.
+Other situations can require a good deal of creativity.
Although we now have two variables, only \isa{xs} is suitable for
-induction, and we repeat our above proof attempt. Unfortunately, we are still
+induction, and we repeat our proof attempt. Unfortunately, we are still
not there:
\begin{isabelle}%
\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}a\ list{\isachardot}\isanewline
@@ -106,12 +113,11 @@
\emph{Generalize goals for induction by universally quantifying all free
variables {\em(except the induction variable itself!)}.}
\end{quote}
-This prevents trivial failures like the above and does not change the
-provability of the goal. Because it is not always required, and may even
-complicate matters in some cases, this heuristic is often not
-applied blindly.
-The variables that require generalization are typically those that
-change in recursive calls.
+This prevents trivial failures like the one above and does not affect the
+validity of the goal. However, this heuristic should not be applied blindly.
+It is not always required, and the additional quantifiers can complicate
+matters in some cases, The variables that should be quantified are typically
+those that change in recursive calls.
A final point worth mentioning is the orientation of the equation we just
proved: the more complex notion (\isa{itrev}) is on the left-hand
@@ -125,12 +131,13 @@
\isa{rev\ xs\ {\isacharat}\ ys} is simpler than \isa{itrev\ xs\ ys}. But see what
happens if you try to prove \isa{rev\ xs\ {\isacharat}\ ys\ {\isacharequal}\ itrev\ xs\ ys}!
-In general, if you have tried the above heuristics and still find your
+If you have tried these heuristics and still find your
induction does not go through, and no obvious lemma suggests itself, you may
need to generalize your proposition even further. This requires insight into
-the problem at hand and is beyond simple rules of thumb. You
-will need to be creative. Additionally, you can read \S\ref{sec:advanced-ind}
+the problem at hand and is beyond simple rules of thumb.
+Additionally, you can read \S\ref{sec:advanced-ind}
to learn about some advanced techniques for inductive proofs.%
+\index{induction heuristics|)}%
\end{isamarkuptext}%
\end{isabellebody}%
%%% Local Variables: