diff -r 93d5408eb7d9 -r fbd097aec213 doc-src/TutorialI/ToyList/document/ToyList.tex --- a/doc-src/TutorialI/ToyList/document/ToyList.tex Sun Oct 21 19:48:19 2001 +0200 +++ b/doc-src/TutorialI/ToyList/document/ToyList.tex Sun Oct 21 19:49:29 2001 +0200 @@ -1,7 +1,8 @@ % \begin{isabellebody}% \def\isabellecontext{ToyList}% -\isacommand{theory}\ ToyList\ {\isacharequal}\ PreList{\isacharcolon}% +\isacommand{theory}\ ToyList\ {\isacharequal}\ PreList{\isacharcolon}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent HOL already has a predefined theory of lists called \isa{List} --- @@ -11,8 +12,10 @@ theory that contains pretty much everything but lists, thus avoiding ambiguities caused by defining lists twice.% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{datatype}\ {\isacharprime}a\ list\ {\isacharequal}\ Nil\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isacharparenleft}{\isachardoublequote}{\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}{\isacharparenright}\isanewline -\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isacharbar}\ Cons\ {\isacharprime}a\ {\isachardoublequote}{\isacharprime}a\ list{\isachardoublequote}\ \ \ \ \ \ \ \ \ \ \ \ {\isacharparenleft}\isakeyword{infixr}\ {\isachardoublequote}{\isacharhash}{\isachardoublequote}\ {\isadigit{6}}{\isadigit{5}}{\isacharparenright}% +\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isacharbar}\ Cons\ {\isacharprime}a\ {\isachardoublequote}{\isacharprime}a\ list{\isachardoublequote}\ \ \ \ \ \ \ \ \ \ \ \ {\isacharparenleft}\isakeyword{infixr}\ {\isachardoublequote}{\isacharhash}{\isachardoublequote}\ {\isadigit{6}}{\isadigit{5}}{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent \index{datatype@\isacommand {datatype} (command)} @@ -44,8 +47,10 @@ \end{warn} Next, two functions \isa{app} and \cdx{rev} are declared:% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{consts}\ app\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\ \ \ {\isacharparenleft}\isakeyword{infixr}\ {\isachardoublequote}{\isacharat}{\isachardoublequote}\ {\isadigit{6}}{\isadigit{5}}{\isacharparenright}\isanewline -\ \ \ \ \ \ \ rev\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}% +\ \ \ \ \ \ \ rev\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent In contrast to many functional programming languages, @@ -57,13 +62,16 @@ \isa{xs\ {\isacharat}\ ys}\index{$HOL2list@\texttt{\at}|bold} becomes the preferred form. Both functions are defined recursively:% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{primrec}\isanewline {\isachardoublequote}{\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ ys\ \ \ \ \ \ \ {\isacharequal}\ ys{\isachardoublequote}\isanewline {\isachardoublequote}{\isacharparenleft}x\ {\isacharhash}\ xs{\isacharparenright}\ {\isacharat}\ ys\ {\isacharequal}\ x\ {\isacharhash}\ {\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}{\isachardoublequote}\isanewline \isanewline +\isamarkupfalse% \isacommand{primrec}\isanewline {\isachardoublequote}rev\ {\isacharbrackleft}{\isacharbrackright}\ \ \ \ \ \ \ \ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline -{\isachardoublequote}rev\ {\isacharparenleft}x\ {\isacharhash}\ xs{\isacharparenright}\ \ {\isacharequal}\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}x\ {\isacharhash}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}{\isachardoublequote}% +{\isachardoublequote}rev\ {\isacharparenleft}x\ {\isacharhash}\ xs{\isacharparenright}\ \ {\isacharequal}\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}x\ {\isacharhash}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}{\isachardoublequote}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent\index{*rev (constant)|(}\index{append function|(} The equations for \isa{app} and \isa{rev} hardly need comments: @@ -102,7 +110,9 @@ To lessen this burden, quotation marks around a single identifier can be dropped, unless the identifier happens to be a keyword, as in% \end{isamarkuptext}% -\isacommand{consts}\ {\isachardoublequote}end{\isachardoublequote}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}% +\isamarkuptrue% +\isacommand{consts}\ {\isachardoublequote}end{\isachardoublequote}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent When Isabelle prints a syntax error message, it refers to the HOL syntax as @@ -122,7 +132,9 @@ Our goal is to show that reversing a list twice produces the original list.% \end{isamarkuptext}% -\isacommand{theorem}\ rev{\isacharunderscore}rev\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs{\isachardoublequote}% +\isamarkuptrue% +\isacommand{theorem}\ rev{\isacharunderscore}rev\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs{\isachardoublequote}\isamarkupfalse% +% \begin{isamarkuptxt}% \index{theorem@\isacommand {theorem} (command)|bold}% \noindent @@ -169,7 +181,9 @@ defined functions are best established by induction. In this case there is nothing obvious except induction on \isa{xs}:% \end{isamarkuptxt}% -\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}% +\isamarkuptrue% +\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptxt}% \noindent\index{*induct_tac (method)}% This tells Isabelle to perform induction on variable \isa{xs}. The suffix @@ -203,7 +217,9 @@ Let us try to solve both goals automatically:% \end{isamarkuptxt}% -\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}% +\isamarkuptrue% +\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptxt}% \noindent This command tells Isabelle to apply a proof strategy called @@ -217,16 +233,21 @@ \end{isabelle} In order to simplify this subgoal further, a lemma suggests itself.% \end{isamarkuptxt}% +\isamarkuptrue% +\isamarkupfalse% % \isamarkupsubsubsection{First Lemma% } +\isamarkuptrue% % \begin{isamarkuptext}% \indexbold{abandoning a proof}\indexbold{proofs!abandoning} After abandoning the above proof attempt (at the shell level type \commdx{oops}) we start a new proof:% \end{isamarkuptext}% -\isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}% +\isamarkuptrue% +\isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isamarkupfalse% +% \begin{isamarkuptxt}% \noindent The keywords \commdx{theorem} and \commdx{lemma} are interchangeable and merely indicate @@ -237,12 +258,16 @@ \isa{ys}. Because \isa{{\isacharat}} is defined by recursion on the first argument, \isa{xs} is the correct one:% \end{isamarkuptxt}% -\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}% +\isamarkuptrue% +\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptxt}% \noindent This time not even the base case is solved automatically:% \end{isamarkuptxt}% -\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}% +\isamarkuptrue% +\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptxt}% \begin{isabelle}% \ {\isadigit{1}}{\isachardot}\ rev\ ys\ {\isacharequal}\ rev\ ys\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}% @@ -251,16 +276,23 @@ first. In the future the step of abandoning an incomplete proof before embarking on the proof of a lemma usually remains implicit.% \end{isamarkuptxt}% +\isamarkuptrue% +\isamarkupfalse% % \isamarkupsubsubsection{Second Lemma% } +\isamarkuptrue% % \begin{isamarkuptext}% We again try the canonical proof procedure:% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{lemma}\ app{\isacharunderscore}Nil{\isadigit{2}}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}xs\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ xs{\isachardoublequote}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline -\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}% +\isamarkupfalse% +\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptxt}% \noindent It works, yielding the desired message \isa{No\ subgoals{\isacharbang}}: @@ -270,7 +302,9 @@ \end{isabelle} We still need to confirm that the proof is now finished:% \end{isamarkuptxt}% -\isacommand{done}% +\isamarkuptrue% +\isacommand{done}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent As a result of that final \commdx{done}, Isabelle associates the lemma just proved @@ -286,9 +320,13 @@ Going back to the proof of the first lemma% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline -\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}% +\isamarkupfalse% +\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isamarkupfalse% +% \begin{isamarkuptxt}% \noindent we find that this time \isa{auto} solves the base case, but the @@ -306,41 +344,61 @@ \end{isabelle} and the missing lemma is associativity of \isa{{\isacharat}}.% \end{isamarkuptxt}% +\isamarkuptrue% +\isamarkupfalse% % \isamarkupsubsubsection{Third Lemma% } +\isamarkuptrue% % \begin{isamarkuptext}% Abandoning the previous attempt, the canonical proof procedure succeeds without further ado.% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{lemma}\ app{\isacharunderscore}assoc\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ {\isacharparenleft}ys\ {\isacharat}\ zs{\isacharparenright}{\isachardoublequote}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isanewline -\isacommand{done}% +\isamarkupfalse% +\isacommand{done}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent Now we can prove the first lemma:% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isanewline -\isacommand{done}% +\isamarkupfalse% +\isacommand{done}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent Finally, we prove our main theorem:% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{theorem}\ rev{\isacharunderscore}rev\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs{\isachardoublequote}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline +\isamarkupfalse% \isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isanewline -\isacommand{done}% +\isamarkupfalse% +\isacommand{done}\isamarkupfalse% +% \begin{isamarkuptext}% \noindent The final \commdx{end} tells Isabelle to close the current theory because we are finished with its development:% \index{*rev (constant)|)}\index{append function|)}% \end{isamarkuptext}% +\isamarkuptrue% \isacommand{end}\isanewline +\isamarkupfalse% \end{isabellebody}% %%% Local Variables: %%% mode: latex