ITP-Course/lectures/15_maintainable_proofs.tex

544 lines
15 KiB
TeX

\part{Maintainable Proofs}
\frame[plain]{\partpage}
\begin{frame}
\frametitle{Motivation}
\begin{itemize}
\item proofs are hopefully still used in a few weeks, months or even years
\item often the environment changes slightly during the lifetime of a proof
\begin{itemize}
\item your definitions change slightly
\item your own lemmata change (\eg become more general)
\item used libraries change
\item HOL changes
\begin{itemize}
\item automation becomes more powerful
\item rewrite rules in certain simpsets change
\item definition packages produce slightly different theorems
\item autogenerated variable-names change
\item \ldots
\end{itemize}
\end{itemize}
\item even if HOL and used libraries are stable, proofs often go through several iterations
\item often they are adapted by someone else than the original author
\item \alert{therefore it is important that proofs are easily maintainable}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Nice Properties of Proofs}
\begin{itemize}
\item maintainability is closely linked to other desirable properties of proofs
\item proofs should be
\begin{itemize}
\item easily understandable
\item well-structured
\item robust
\begin{itemize}
\item they should be able to cope with minor changes to environment
\item if they fail they should do so at sensible points
\end{itemize}
\item reusable
\end{itemize}
\item How can one write proofs with such properties?
\item as usual, there are no easy answers but plenty of good advice
\item I recommend following the advice of \emph{ProofStyle} manual
\item parts of this advice as well as a few extra points are discussed in the following
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Formatting}
\begin{itemize}
\item format your proof such that it easily understandable
\item make the structure of the proof very clear
\item \alert{show clearly where subgoals start and stop}
\item use indentation to mark proofs of subgoals
\item use empty lines to separate large proofs of subgoals
\item use comments where appropriate
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Formatting Example I}
\begin{alertblock}{Bad Example Term Formatting}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> LENGTH l2 <
LENGTH (l1 ++ l2)``,
...)
\end{semiverbatim}
\end{alertblock}
\begin{exampleblock}{Good Example Term Formatting}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==>
(LENGTH l2 < LENGTH (l1 ++ l2))``,
...)
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Formatting Example II}
\begin{alertblock}{Bad Example Subgoals}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >>
REWRITE_TAC[] >>
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >>
DECIDE_TAC)
\end{semiverbatim}
\end{alertblock}
\begin{alertblock}{Improved Example Subgoals}
At least show when a subgoal starts and ends
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >> (
REWRITE_TAC[]
) >>
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >>
DECIDE_TAC)
\end{semiverbatim}
\end{alertblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Formatting Example II 2}
\begin{exampleblock}{Good Example Subgoals}
Make sure \texttt{REWRITE\_TAC} is only applied to first subgoal and
proof fails, if it does not solve this subgoal.
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >- (
REWRITE_TAC[]
) >>
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >>
DECIDE_TAC)
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Formatting Example II 3}
\begin{exampleblock}{Alternative Good Example Subgoals}
Alternative good formatting using \texttt{THENL}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >| [
REWRITE_TAC[],
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >>
DECIDE_TAC
])
\end{semiverbatim}
\end{exampleblock}
\begin{alertblock}{Another Bad Example Subgoals}
Bad formatting using \texttt{THENL}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >| [REWRITE_TAC[],
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >> DECIDE_TAC])
\end{semiverbatim}
\end{alertblock}
\end{frame}
\begin{frame}
\frametitle{Some basic advice}
\begin{itemize}
\item use semicoli after each declaration
\begin{itemize}
\item if exception is raised during interactive processing (\eg by a failing proof), previous successful declarations are kept
\item it sometimes leads to better error messages in case of parsing errors
\end{itemize}
\item use plenty of parentheses to make structure very clear
\item don't ignore parser warnings
\begin{itemize}
\item especially warnings about multiple possible parse trees are likely to lead to unstable proofs
\item understand why such warnings occur and make sure there is no problem
\end{itemize}
\item format your development well
\begin{itemize}
\item use indentation
\item use linebreaks at sensible points
\item don't use overlong lines
\item \ldots
\end{itemize}
\item don't use \ml{open} in middle of files
\item personal opinion: avoid unicode in source files
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{KISS and Premature Optimisation}
\begin{itemize}
\item follow standard design principles
\begin{itemize}
\item \emph{KISS} principle
\item ``\emph{premature optimization is the root of all evil}'' (Donald Knuth)
\end{itemize}
\item don't try to be overly clever
\item simple proofs are preferable
\item proof-checking-speed mostly unimportant
\item conciseness not a value in itself but desirable if it helps
\begin{itemize}
\item readability
\item maintainability
\end{itemize}
\item abstraction is often desirable, but also has a price
\begin{itemize}
\item don't use too complex, artificial definitions and lemmata
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Too much abstraction}
\begin{alertblock}{Too much abstraction Example}
\begin{semiverbatim}\scriptsize
val TOO_ABSTRACT_LEMMA = prove (``
!(size :'a -> num) (P : 'a -> bool) (combine : 'a -> 'a -> 'a).
(!x. P x ==> (0 < size x)) \holAnd{}
(!x1 x2. size x1 + size x2 <= size (combine x1 x2)) ==>
(!x1 x2. P x1 ==> (size x2 < size (combine x1 x2)))``,
...)
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
\textrm{some proof using} ABSTRACT_LEMMA
)
\end{semiverbatim}
\end{alertblock}
\end{frame}
\begin{frame}
\frametitle{Too clever tactics}
\begin{itemize}
\item a common mistake is to use too clever tactics
\begin{itemize}
\item intended to work on many (sub)goals
\item using \hol{TRY} and other fancy trial and error mechanisms
\item intended to replace multiple simple, clear tactics
\end{itemize}
\item typical case: a tactic containing \hol{TRY} applied to many subgoals
\item it is often hard to see why such tactics work
\item if something goes wrong, they are hard to debug
\item general advice: don't factor with tactics, instead use definitions and lemmata
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Too Clever Tactics Example I}
\begin{alertblock}{Bad Example Subgoals}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >> (
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >>
DECIDE_TAC
))
\end{semiverbatim}
\end{alertblock}
\begin{exampleblock}{Alternative Good Example Subgoals II}
\begin{semiverbatim}\scriptsize
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >> SIMP_TAC list_ss [])
prove (``!l1 l2. l1 <> [] ==> (LENGTH l2 < LENGTH (l1 ++ l2))``,
Cases >| [
REWRITE_TAC[],
REWRITE_TAC[listTheory.LENGTH, listTheory.LENGTH_APPEND] >>
REPEAT STRIP_TAC >>
DECIDE_TAC
])
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Too Clever Tactics Example II}
\begin{alertblock}{Bad Example}
\begin{semiverbatim}\scriptsize
val oadd_def = Define `(oadd (SOME n1) (SOME n2) = (SOME (n1 + n2))) \holAnd{}
(oadd _ _ = NONE)`;
val osub_def = Define `(osub (SOME n1) (SOME n2) = (SOME (n1 - n2))) \holAnd{}
(osub _ _ = NONE)`;
val omul_def = Define `(omul (SOME n1) (SOME n2) = (SOME (n1 * n2))) \holAnd{}
(omul _ _ = NONE)`;
val obin_NONE_TAC =
Cases_on `o1` >> Cases_on `o2` >>
SIMP_TAC std_ss [oadd_def, osub_def, omul_def];
val oadd_NONE = prove (
``!o1 o2. (oadd o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
obin_NONE_TAC);
val osub_NONE = prove (
``!o1 o2. (osub o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
obin_NONE_TAC);
val omul_NONE = prove (
``!o1 o2. (omul o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
obin_NONE_TAC);
\end{semiverbatim}
\end{alertblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Too Clever Tactics Example II}
\begin{exampleblock}{Good Example}
\begin{semiverbatim}\scriptsize
val obin_def = Define `(obin op (SOME n1) (SOME n2) = (SOME (op n1 n2))) \holAnd{}
(obin _ _ _ = NONE)`;
val oadd_def = Define `oadd = obin \$+`;
val osub_def = Define `osub = obin \$-`;
val omul_def = Define `omul = obin \$*`;
val obin_NONE = prove (
``!op o1 o2. (obin op o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
Cases_on `o1` >> Cases_on `o2` >> SIMP_TAC std_ss [obin_def]);
val oadd_NONE = prove (
``!o1 o2. (oadd o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
REWRITE_TAC[oadd_def, obin_NONE]);
val osub_NONE = prove (
``!o1 o2. (osub o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
REWRITE_TAC[osub_def, obin_NONE]);
val omul_NONE = prove (
``!o1 o2. (omul o1 o2 = NONE) <=> (o1 = NONE) \holOr{} (o2 = NONE)``,
REWRITE_TAC[omul_def, obin_NONE]);
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Use many subgoals and lemmata}
\begin{itemize}
\item often it is beneficial to use subgoals
\begin{itemize}
\item they structure long proofs well
\item they help keeping the proof state clean
\item they mark clearly what one tries to proof
\item they provide points where proofs can break sensibly
\end{itemize}
\item general enough subgoals should become lemmata
\begin{itemize}
\item this improves reusability
\item proof script for main lemma becomes shorter
\item proofs are disentangled
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Subgoal Example}
\begin{itemize}
\item the following example is taken from exercise 5
\item we try to prove \hol{\texttt{!l.\ IS\_WEAK\_SUBLIST\_FILTER l l}}
\item given are following definitions and lemmata
\end{itemize}
\begin{block}{}
\begin{semiverbatim}\scriptsize
val FILTER_BY_BOOLS_def = Define `
FILTER_BY_BOOLS bl l = MAP SND (FILTER FST (ZIP (bl, l)))`;
val IS_WEAK_SUBLIST_FILTER_def = Define `IS_WEAK_SUBLIST_FILTER l1 l2 =
?(bl : bool list). (LENGTH bl = LENGTH l1) \holAnd{} (l2 = FILTER_BY_BOOLS bl l1)`;
val FILTER_BY_BOOLS_REWRITES = store_thm ("FILTER_BY_BOOLS_REWRITES",
``(FILTER_BY_BOOLS [] [] = []) \holAnd{}
(!b bl x xs. (FILTER_BY_BOOLS (b::bl) (x::xs) =
if b then x::(FILTER_BY_BOOLS bl xs) else FILTER_BY_BOOLS bl xs))``,
REWRITE_TAC [FILTER_BY_BOOLS_def, ZIP, MAP, FILTER] >>
Cases_on `b` >> REWRITE_TAC [MAP]);
\end{semiverbatim}
\end{block}
\end{frame}
\begin{frame}[fragile]
\frametitle{Subgoal Example II}
\begin{alertblock}{First Version}
\begin{semiverbatim}\scriptsize
val IS_WEAK_SUBLIST_FILTER_REFL = store_thm ("IS_WEAK_SUBLIST_FILTER_REFL",
``!l. IS_WEAK_SUBLIST_FILTER l l``,
REWRITE_TAC[IS_WEAK_SUBLIST_FILTER_def] >>
Induct_on `l` >- (
Q.EXISTS_TAC `[]` >>
SIMP_TAC list_ss [FILTER_BY_BOOLS_REWRITES]
) >>
FULL_SIMP_TAC std_ss [] >>
GEN_TAC >>
Q.EXISTS_TAC `T::bl` >>
ASM_SIMP_TAC list_ss [FILTER_BY_BOOLS_REWRITES])
\end{semiverbatim}
\end{alertblock}
\begin{itemize}
\item the proof mixes properties of \texttt{IS\_WEAK\_SUBLIST\_FILTER} and
properties of \texttt{FILTER\_BY\_BOOLS}
\item it is hard to see what the main idea is
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Subgoal Example III}
\begin{itemize}
\item the following proof separates the property of \texttt{FILTER\_BY\_BOOLS} as a subgoal
\item the main idea becomes clearer
\end{itemize}
\begin{exampleblock}{Subgoal Version}
\begin{semiverbatim}\scriptsize
val IS_WEAK_SUBLIST_FILTER_REFL = store_thm ("IS_WEAK_SUBLIST_FILTER_REFL",
``!l. IS_WEAK_SUBLIST_FILTER l l``,
GEN_TAC >>
REWRITE_TAC[IS_WEAK_SUBLIST_FILTER_def] >>
`FILTER_BY_BOOLS (REPLICATE (LENGTH l) T) l = l` suffices_by (
METIS_TAC[LENGTH_REPLICATE]
) >>
Induct_on `l` >> (
ASM_SIMP_TAC list_ss [FILTER_BY_BOOLS_REWRITES, REPLICATE]
))
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Subgoal Example IV}
\begin{itemize}
\item the subgoal is general enough to justify a lemma
\item the structure becomes even cleaner
\item this improves reusability
\end{itemize}
\begin{exampleblock}{Lemma Version}
\begin{semiverbatim}\scriptsize
val FILTER_BY_BOOLS_REPL_T = store_thm ("FILTER_BY_BOOLS_REPL_T",
``!l. FILTER_BY_BOOLS (REPLICATE (LENGTH l) T) l = l``,
Induct >> ASM_REWRITE_TAC [REPLICATE, FILTER_BY_BOOLS_REWRITES, LENGTH]);
val IS_WEAK_SUBLIST_FILTER_REFL = store_thm ("IS_WEAK_SUBLIST_FILTER_REFL",
``!l. IS_WEAK_SUBLIST_FILTER l l``,
GEN_TAC >>
REWRITE_TAC[IS_WEAK_SUBLIST_FILTER_def] >>
Q.EXISTS_TAC `REPLICATE (LENGTH l) T` >>
SIMP_TAC list_ss [FILTER_BY_BOOLS_REPL_T, LENGTH_REPLICATE])
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}[fragile]
\frametitle{Avoid Autogenerated Names}
\begin{itemize}
\item many HOL-tactics introduce new variable names
\begin{itemize}
\item \hol{Induct}
\item \hol{Cases}
\item \ldots
\end{itemize}
\item the new names are often very artificial
\item even worse, generated names might change in future
\item proof scripts using autogenerated names are therefore
\begin{itemize}
\item hard to read
\item potentially fragile
\end{itemize}
\item therefore rename variables after they have been introduced
\item HOL has multiple tactics supporting renaming
\item most useful is \hol{rename1 `pat`}, it searches for pattern and renames vars accordingly
\end{itemize}
\end{frame}
\begin{frame}[fragile]
\frametitle{Autogenerated Names Example}
\begin{alertblock}{Bad Example}
\begin{semiverbatim}\scriptsize
prove (``!l. 1 < LENGTH l ==> (?x1 x2 l'. l = x1::x2::l')``,
GEN_TAC >>
Cases_on `l` >> SIMP_TAC list_ss [] >>
Cases_on `t` >> SIMP_TAC list_ss [])
\end{semiverbatim}
\end{alertblock}
\begin{exampleblock}{Good Example}
\begin{semiverbatim}\scriptsize
prove (``!l. 1 < LENGTH l ==> (?x1 x2 l'. l = x1::x2::l')``,
GEN_TAC >>
Cases_on `l` >> SIMP_TAC list_ss [] >>
rename1 `LENGTH l2` >>
Cases_on `l2` >> SIMP_TAC list_ss [])
\end{semiverbatim}
\end{exampleblock}
\begin{block}{Proof State before \hol{rename1}}
\begin{semiverbatim}\scriptsize
1 < SUC (LENGTH t) ==> ?x2 l'. t = x2::l'
\end{semiverbatim}
\end{block}
\begin{block}{Proof State after \hol{rename1}}
\begin{semiverbatim}\scriptsize
1 < SUC (LENGTH l2) ==> ?x2 l'. l2 = x2::l'
\end{semiverbatim}
\end{block}
\end{frame}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "current"
%%% End: