doc-src/TutorialI/ToyList/ToyList.thy
changeset 8771 026f37a86ea7
parent 8745 13b32661dde4
child 9458 c613cd06d5cf
equal deleted inserted replaced
8770:bfab4d4b7516 8771:026f37a86ea7
     1 theory ToyList = PreList:
     1 theory ToyList = PreList:
     2 
     2 
     3 text{*\noindent
     3 text{*\noindent
     4 HOL already has a predefined theory of lists called \texttt{List} ---
     4 HOL already has a predefined theory of lists called \isa{List} ---
     5 \texttt{ToyList} is merely a small fragment of it chosen as an example. In
     5 \isa{ToyList} is merely a small fragment of it chosen as an example. In
     6 contrast to what is recommended in \S\ref{sec:Basic:Theories},
     6 contrast to what is recommended in \S\ref{sec:Basic:Theories},
     7 \texttt{ToyList} is not based on \texttt{Main} but on \texttt{PreList}, a
     7 \isa{ToyList} is not based on \isa{Main} but on \isa{PreList}, a
     8 theory that contains pretty much everything but lists, thus avoiding
     8 theory that contains pretty much everything but lists, thus avoiding
     9 ambiguities caused by defining lists twice.
     9 ambiguities caused by defining lists twice.
    10 *}
    10 *}
    11 
    11 
    12 datatype 'a list = Nil                          ("[]")
    12 datatype 'a list = Nil                          ("[]")
    29 the right, i.e.\ the term \isa{$x$ \# $y$ \# $z$} is read as \isa{$x$
    29 the right, i.e.\ the term \isa{$x$ \# $y$ \# $z$} is read as \isa{$x$
    30 \# ($y$ \# $z$)} and not as \isa{($x$ \# $y$) \# $z$}.
    30 \# ($y$ \# $z$)} and not as \isa{($x$ \# $y$) \# $z$}.
    31 
    31 
    32 \begin{warn}
    32 \begin{warn}
    33   Syntax annotations are a powerful but completely optional feature. You
    33   Syntax annotations are a powerful but completely optional feature. You
    34   could drop them from theory \texttt{ToyList} and go back to the identifiers
    34   could drop them from theory \isa{ToyList} and go back to the identifiers
    35   \isa{Nil} and \isa{Cons}. However, lists are such a central datatype
    35   \isa{Nil} and \isa{Cons}. However, lists are such a central datatype
    36   that their syntax is highly customized. We recommend that novices should
    36   that their syntax is highly customized. We recommend that novices should
    37   not use syntax annotations in their own theories.
    37   not use syntax annotations in their own theories.
    38 \end{warn}
    38 \end{warn}
    39 Next, two functions \isa{app} and \isaindexbold{rev} are declared:
    39 Next, two functions \isa{app} and \isaindexbold{rev} are declared:
    65 \noindent
    65 \noindent
    66 The equations for \isa{app} and \isa{rev} hardly need comments:
    66 The equations for \isa{app} and \isa{rev} hardly need comments:
    67 \isa{app} appends two lists and \isa{rev} reverses a list.  The keyword
    67 \isa{app} appends two lists and \isa{rev} reverses a list.  The keyword
    68 \isacommand{primrec}\index{*primrec} indicates that the recursion is of a
    68 \isacommand{primrec}\index{*primrec} indicates that the recursion is of a
    69 particularly primitive kind where each recursive call peels off a datatype
    69 particularly primitive kind where each recursive call peels off a datatype
    70 constructor from one of the arguments (see \S\ref{sec:datatype}).  Thus the
    70 constructor from one of the arguments.  Thus the
    71 recursion always terminates, i.e.\ the function is \bfindex{total}.
    71 recursion always terminates, i.e.\ the function is \bfindex{total}.
    72 
    72 
    73 The termination requirement is absolutely essential in HOL, a logic of total
    73 The termination requirement is absolutely essential in HOL, a logic of total
    74 functions. If we were to drop it, inconsistencies would quickly arise: the
    74 functions. If we were to drop it, inconsistencies would quickly arise: the
    75 ``definition'' $f(n) = f(n)+1$ immediately leads to $0 = 1$ by subtracting
    75 ``definition'' $f(n) = f(n)+1$ immediately leads to $0 = 1$ by subtracting
   101 
   101 
   102 consts "end" :: "'a list \\<Rightarrow> 'a"
   102 consts "end" :: "'a list \\<Rightarrow> 'a"
   103 
   103 
   104 text{*\noindent
   104 text{*\noindent
   105 When Isabelle prints a syntax error message, it refers to the HOL syntax as
   105 When Isabelle prints a syntax error message, it refers to the HOL syntax as
   106 the \bfindex{inner syntax}.
   106 the \bfindex{inner syntax} and the enclosing theory language as the \bfindex{outer syntax}.
   107 
   107 
   108 
   108 
   109 \section{An introductory proof}
   109 \section{An introductory proof}
   110 \label{sec:intro-proof}
   110 \label{sec:intro-proof}
   111 
   111 
   120 list. The input line
   120 list. The input line
   121 *}
   121 *}
   122 
   122 
   123 theorem rev_rev [simp]: "rev(rev xs) = xs";
   123 theorem rev_rev [simp]: "rev(rev xs) = xs";
   124 
   124 
   125 txt{*\noindent\index{*theorem|bold}\index{*simp (attribute)|bold}
   125 txt{*\index{*theorem|bold}\index{*simp (attribute)|bold}
   126 \begin{itemize}
   126 \begin{itemize}
   127 \item
   127 \item
   128 establishes a new theorem to be proved, namely \isa{rev(rev xs) = xs},
   128 establishes a new theorem to be proved, namely \isa{rev(rev xs) = xs},
   129 \item
   129 \item
   130 gives that theorem the name \isa{rev_rev} by which it can be referred to,
   130 gives that theorem the name \isa{rev_rev} by which it can be referred to,
   218 (*>*)
   218 (*>*)
   219 
   219 
   220 text{*
   220 text{*
   221 \subsubsection*{First lemma: \texttt{rev(xs \at~ys) = (rev ys) \at~(rev xs)}}
   221 \subsubsection*{First lemma: \texttt{rev(xs \at~ys) = (rev ys) \at~(rev xs)}}
   222 
   222 
   223 After abandoning the above proof attempt (at the shell level type
   223 After abandoning the above proof attempt\indexbold{abandon proof} (at the shell level type
   224 \isa{oops}) we start a new proof:
   224 \isacommand{oops}) we start a new proof:
   225 *}
   225 *}
   226 
   226 
   227 lemma rev_app [simp]: "rev(xs @ ys) = (rev ys) @ (rev xs)";
   227 lemma rev_app [simp]: "rev(xs @ ys) = (rev ys) @ (rev xs)";
   228 
   228 
   229 txt{*\noindent The keywords \isacommand{theorem}\index{*theorem} and
   229 txt{*\noindent The keywords \isacommand{theorem}\index{*theorem} and
   230 \isacommand{lemma}\indexbold{*lemma} are interchangable and merely indicate
   230 \isacommand{lemma}\indexbold{*lemma} are interchangable and merely indicate
   231 the importance we attach to a proposition. In general, we use the words
   231 the importance we attach to a proposition. In general, we use the words
   232 \emph{theorem}\index{theorem} and \emph{lemma}\index{lemma} pretty much
   232 \emph{theorem}\index{theorem} and \emph{lemma}\index{lemma} pretty much
   233 interchangeably.
   233 interchangeably.
   234 
   234 
   235 %FIXME indent!
       
   236 There are two variables that we could induct on: \isa{xs} and
   235 There are two variables that we could induct on: \isa{xs} and
   237 \isa{ys}. Because \isa{\at} is defined by recursion on
   236 \isa{ys}. Because \isa{\at} is defined by recursion on
   238 the first argument, \isa{xs} is the correct one:
   237 the first argument, \isa{xs} is the correct one:
   239 *}
   238 *}
   240 
   239 
   249 txt{*
   248 txt{*
   250 \begin{isabellepar}%
   249 \begin{isabellepar}%
   251 ~1.~rev~ys~=~rev~ys~@~[]\isanewline
   250 ~1.~rev~ys~=~rev~ys~@~[]\isanewline
   252 ~2. \dots
   251 ~2. \dots
   253 \end{isabellepar}%
   252 \end{isabellepar}%
   254 We need to cancel this proof attempt and prove another simple lemma first.
   253 Again, we need to abandon this proof attempt and prove another simple lemma first.
   255 In the future the step of cancelling an incomplete proof before embarking on
   254 In the future the step of abandoning an incomplete proof before embarking on
   256 the proof of a lemma often remains implicit.
   255 the proof of a lemma usually remains implicit.
   257 *}
   256 *}
   258 (*<*)
   257 (*<*)
   259 oops
   258 oops
   260 (*>*)
   259 (*>*)
   261 
   260