64 and can be skipped by casual readers. |
64 and can be skipped by casual readers. |
65 |
65 |
66 There are two kinds of commands used during a proof: the actual proof |
66 There are two kinds of commands used during a proof: the actual proof |
67 commands and auxiliary commands for examining the proof state and controlling |
67 commands and auxiliary commands for examining the proof state and controlling |
68 the display. Simple proof commands are of the form |
68 the display. Simple proof commands are of the form |
69 \isacommand{apply}\isa{(method)}\indexbold{apply} where \bfindex{method} is a |
69 \commdx{apply}\isa{(method)}, where \isa{method} is typically |
70 synonym for ``theorem proving function''. Typical examples are |
70 \isa{induct_tac} or \isa{auto}. All such theorem proving operations |
71 \isa{induct_tac} and \isa{auto}. Further methods are introduced throughout |
71 are referred to as \bfindex{methods}, and further ones are |
72 the tutorial. Unless stated otherwise you may assume that a method attacks |
72 introduced throughout the tutorial. Unless stated otherwise, you may |
73 merely the first subgoal. An exception is \isa{auto} which tries to solve all |
73 assume that a method attacks merely the first subgoal. An exception is |
74 subgoals. |
74 \isa{auto}, which tries to solve all subgoals. |
75 |
75 |
76 The most useful auxiliary commands are: |
76 The most useful auxiliary commands are as follows: |
77 \begin{description} |
77 \begin{description} |
78 \item[Undoing:] \isacommand{undo}\indexbold{*undo} undoes the effect of the |
78 \item[Undoing:] \commdx{undo} undoes the effect of |
|
79 the |
79 last command; \isacommand{undo} can be undone by |
80 last command; \isacommand{undo} can be undone by |
80 \isacommand{redo}\indexbold{*redo}. Both are only needed at the shell |
81 \commdx{redo}. Both are only needed at the shell |
81 level and should not occur in the final theory. |
82 level and should not occur in the final theory. |
82 \item[Printing the current state:] \isacommand{pr}\indexbold{*pr} redisplays |
83 \item[Printing the current state:] \commdx{pr} |
|
84 redisplays |
83 the current proof state, for example when it has scrolled past the top of |
85 the current proof state, for example when it has scrolled past the top of |
84 the screen. |
86 the screen. |
85 \item[Limiting the number of subgoals:] \isacommand{pr}~$n$ tells Isabelle to |
87 \item[Limiting the number of subgoals:] \isacommand{pr}~$n$ tells Isabelle to |
86 print only the first $n$ subgoals from now on and redisplays the current |
88 print only the first $n$ subgoals from now on and redisplays the current |
87 proof state. This is helpful when there are many subgoals. |
89 proof state. This is helpful when there are many subgoals. |
88 \item[Modifying the order of subgoals:] |
90 \item[Modifying the order of subgoals:] |
89 \isacommand{defer}\indexbold{*defer} moves the first subgoal to the end and |
91 \commdx{defer} moves the first subgoal to the end and |
90 \isacommand{prefer}\indexbold{*prefer}~$n$ moves subgoal $n$ to the front. |
92 \commdx{prefer}~$n$ moves subgoal $n$ to the front. |
91 \item[Printing theorems:] |
93 \item[Printing theorems:] |
92 \isacommand{thm}\indexbold{*thm}~\textit{name}$@1$~\dots~\textit{name}$@n$ |
94 \commdx{thm}~\textit{name}$@1$~\dots~\textit{name}$@n$ |
93 prints the named theorems. |
95 prints the named theorems. |
94 \item[Displaying types:] We have already mentioned the flag |
96 \item[Displaying types:] We have already mentioned the flag |
95 \ttindex{show_types} above. It can also be useful for detecting typos in |
97 \ttindex{show_types} above. It can also be useful for detecting typos in |
96 formulae early on. For example, if \texttt{show_types} is set and the goal |
98 formulae early on. For example, if \texttt{show_types} is set and the goal |
97 \isa{rev(rev xs) = xs} is started, Isabelle prints the additional output |
99 \isa{rev(rev xs) = xs} is started, Isabelle prints the additional output |
110 ~~re~::~'a~list~{\isasymRightarrow}~'a~list\isanewline |
112 ~~re~::~'a~list~{\isasymRightarrow}~'a~list\isanewline |
111 ~~xs~::~'a~list% |
113 ~~xs~::~'a~list% |
112 \end{isabelle}% |
114 \end{isabelle}% |
113 \par\noindent |
115 \par\noindent |
114 would have alerted us because of the unexpected variable \isa{re}. |
116 would have alerted us because of the unexpected variable \isa{re}. |
115 \item[Reading terms and types:] \isacommand{term}\indexbold{*term} |
117 \item[Reading terms and types:] \commdx{term} |
116 \textit{string} reads, type-checks and prints the given string as a term in |
118 \textit{string} reads, type-checks and prints the given string as a term in |
117 the current context; the inferred type is output as well. |
119 the current context; the inferred type is output as well. |
118 \isacommand{typ}\indexbold{*typ} \textit{string} reads and prints the given |
120 \commdx{typ} \textit{string} reads and prints the given |
119 string as a type in the current context. |
121 string as a type in the current context. |
120 \item[(Re)loading theories:] When you start your interaction you must open a |
122 \item[(Re)loading theories:] When you start your interaction you must open a |
121 named theory with the line \isa{\isacommand{theory}~T~=~\dots~:}. Isabelle |
123 named theory with the line \isa{\isacommand{theory}~T~=~\dots~:}. Isabelle |
122 automatically loads all the required parent theories from their respective |
124 automatically loads all the required parent theories from their respective |
123 files (which may take a moment, unless the theories are already loaded and |
125 files (which may take a moment, unless the theories are already loaded and |
124 the files have not been modified). |
126 the files have not been modified). |
125 |
127 |
126 If you suddenly discover that you need to modify a parent theory of your |
128 If you suddenly discover that you need to modify a parent theory of your |
127 current theory, you must first abandon your current theory\indexbold{abandon |
129 current theory, you must first abandon your current theory\indexbold{abandon |
128 theory}\indexbold{theory!abandon} (at the shell |
130 theory}\indexbold{theory!abandon} (at the shell |
129 level type \isacommand{kill}\indexbold{*kill}). After the parent theory has |
131 level type \commdx{kill}). After the parent theory has |
130 been modified, you go back to your original theory. When its first line |
132 been modified, you go back to your original theory. When its first line |
131 \isa{\isacommand{theory}~T~=~\dots~:} is processed, the |
133 \isa{\isacommand{theory}~T~=~\dots~:} is processed, the |
132 modified parent is reloaded automatically. |
134 modified parent is reloaded automatically. |
133 |
135 |
134 % The only time when you need to load a theory by hand is when you simply |
136 % The only time when you need to load a theory by hand is when you simply |
135 % want to check if it loads successfully without wanting to make use of the |
137 % want to check if it loads successfully without wanting to make use of the |
136 % theory itself. This you can do by typing |
138 % theory itself. This you can do by typing |
137 % \isa{\isacommand{use\_thy}\indexbold{*use_thy}~"T"}. |
139 % \isa{\commdx{use\_thy}~"T"}. |
138 \end{description} |
140 \end{description} |
139 Further commands are found in the Isabelle/Isar Reference Manual. |
141 Further commands are found in the Isabelle/Isar Reference Manual. |
140 |
142 |
141 We now examine Isabelle's functional programming constructs systematically, |
143 We now examine Isabelle's functional programming constructs systematically, |
142 starting with inductive datatypes. |
144 starting with inductive datatypes. |
157 Lists are one of the essential datatypes in computing. Readers of this |
159 Lists are one of the essential datatypes in computing. Readers of this |
158 tutorial and users of HOL need to be familiar with their basic operations. |
160 tutorial and users of HOL need to be familiar with their basic operations. |
159 Theory \isa{ToyList} is only a small fragment of HOL's predefined theory |
161 Theory \isa{ToyList} is only a small fragment of HOL's predefined theory |
160 \isa{List}\footnote{\url{http://isabelle.in.tum.de/library/HOL/List.html}}. |
162 \isa{List}\footnote{\url{http://isabelle.in.tum.de/library/HOL/List.html}}. |
161 The latter contains many further operations. For example, the functions |
163 The latter contains many further operations. For example, the functions |
162 \isaindexbold{hd} (``head'') and \isaindexbold{tl} (``tail'') return the first |
164 \cdx{hd} (``head'') and \cdx{tl} (``tail'') return the first |
163 element and the remainder of a list. (However, pattern-matching is usually |
165 element and the remainder of a list. (However, pattern-matching is usually |
164 preferable to \isa{hd} and \isa{tl}.) |
166 preferable to \isa{hd} and \isa{tl}.) |
165 Also available are higher-order functions like \isa{map} and \isa{filter}. |
167 Also available are higher-order functions like \isa{map} and \isa{filter}. |
166 Theory \isa{List} also contains |
168 Theory \isa{List} also contains |
167 more syntactic sugar: \isa{[}$x@1$\isa{,}\dots\isa{,}$x@n$\isa{]} abbreviates |
169 more syntactic sugar: \isa{[}$x@1$\isa{,}\dots\isa{,}$x@n$\isa{]} abbreviates |
190 primitive recursive function definitions. |
192 primitive recursive function definitions. |
191 |
193 |
192 Every datatype $t$ comes equipped with a \isa{size} function from $t$ into |
194 Every datatype $t$ comes equipped with a \isa{size} function from $t$ into |
193 the natural numbers (see~{\S}\ref{sec:nat} below). For lists, \isa{size} is |
195 the natural numbers (see~{\S}\ref{sec:nat} below). For lists, \isa{size} is |
194 just the length, i.e.\ \isa{size [] = 0} and \isa{size(x \# xs) = size xs + |
196 just the length, i.e.\ \isa{size [] = 0} and \isa{size(x \# xs) = size xs + |
195 1}. In general, \isaindexbold{size} returns \isa{0} for all constructors |
197 1}. In general, \cdx{size} returns \isa{0} for all constructors |
196 that do not have an argument of type $t$, and for all other constructors |
198 that do not have an argument of type $t$, and for all other constructors |
197 \isa{1 +} the sum of the sizes of all arguments of type $t$. Note that because |
199 \isa{1 +} the sum of the sizes of all arguments of type $t$. Note that because |
198 \isa{size} is defined on every datatype, it is overloaded; on lists |
200 \isa{size} is defined on every datatype, it is overloaded; on lists |
199 \isa{size} is also called \isaindexbold{length}, which is not overloaded. |
201 \isa{size} is also called \sdx{length}, which is not overloaded. |
200 Isabelle will always show \isa{size} on lists as \isa{length}. |
202 Isabelle will always show \isa{size} on lists as \isa{length}. |
201 |
203 |
202 |
204 |
203 \subsection{Primitive Recursion} |
205 \subsection{Primitive Recursion} |
204 |
206 |