equal
deleted
inserted
replaced
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 |