1 \chapter{Basic Concepts}
5 This is a tutorial on how to use the theorem prover Isabelle/HOL as a specification and
6 verification system. Isabelle is a generic system for implementing logical
7 formalisms, and Isabelle/HOL is the specialization of Isabelle for
8 HOL, which abbreviates Higher-Order Logic. We introduce HOL step by step
10 \[ \mbox{HOL} = \mbox{Functional Programming} + \mbox{Logic}. \]
11 We do not assume that the reader is familiar with mathematical logic but that
12 (s)he is used to logical and set theoretic notation. In contrast, we do assume
13 that the reader is familiar with the basic concepts of functional programming.
14 For excellent introductions consult the textbooks by Bird and
15 Wadler~\cite{Bird-Wadler} or Paulson~\cite{paulson-ml2}. Although this
16 tutorial initially concentrates on functional programming, do not be
17 misled: HOL can express most mathematical concepts, and functional programming
18 is just one particularly simple and ubiquitous instance.
20 Isabelle~\cite{paulson-isa-book} is implemented in ML~\cite{SML}. This has
21 influenced some of Isabelle/HOL's concrete syntax but is otherwise irrelevant
22 for us because this tutorial is based on
23 Isabelle/Isar~\cite{isabelle-isar-ref}, an extension of Isabelle with
24 structured proofs. Thus the full name of the system should be
25 Isabelle/Isar/HOL, but that is a bit of a mouthful. There are other
26 implementations of HOL, in particular the one by Mike Gordon \emph{et al.},
27 which is usually referred to as ``the HOL system'' \cite{mgordon-hol}. For us,
28 HOL refers to the logical system, and sometimes its incarnation Isabelle/HOL.
30 A tutorial is by definition incomplete. Currently the tutorial only
31 introduces the rudiments of Isar's proof language. To fully exploit the power
32 of Isar you need to consult the Isabelle/Isar Reference
33 Manual~\cite{isabelle-isar-ref}. If you want to use Isabelle's ML level
34 directly (for example for writing your own proof procedures) see the Isabelle
35 Reference Manual~\cite{isabelle-ref}; for details relating to HOL see the
36 Isabelle/HOL manual~\cite{isabelle-HOL}. All manuals have a comprehensive
40 \label{sec:Basic:Theories}
42 Working with Isabelle means creating theories. Roughly speaking, a
43 \bfindex{theory} is a named collection of types, functions, and theorems,
44 much like a module in a programming language or a specification in a
45 specification language. In fact, theories in HOL can be either. The general
46 format of a theory \texttt{T} is
48 theory T = B\(@1\) + \(\cdots\) + B\(@n\):
49 \(\textit{declarations, definitions, and proofs}\)
52 where \texttt{B}$@1$, \dots, \texttt{B}$@n$ are the names of existing
53 theories that \texttt{T} is based on and \texttt{\textit{declarations,
54 definitions, and proofs}} represents the newly introduced concepts
55 (types, functions etc.) and proofs about them. The \texttt{B}$@i$ are the
56 direct \textbf{parent theories}\indexbold{parent theory} of \texttt{T}.
57 Everything defined in the parent theories (and their parents \dots) is
58 automatically visible. To avoid name clashes, identifiers can be
59 \textbf{qualified} by theory names as in \texttt{T.f} and
60 \texttt{B.f}.\indexbold{identifier!qualified} Each theory \texttt{T} must
61 reside in a \bfindex{theory file} named \texttt{T.thy}.
63 This tutorial is concerned with introducing you to the different linguistic
64 constructs that can fill \textit{\texttt{declarations, definitions, and
65 proofs}} in the above theory template. A complete grammar of the basic
66 constructs is found in the Isabelle/Isar Reference Manual.
68 HOL's theory collection is available online at
70 \url{http://isabelle.in.tum.de/library/HOL/}
72 and is recommended browsing. Note that most of the theories
73 are based on classical Isabelle without the Isar extension. This means that
74 they look slightly different than the theories in this tutorial, and that all
75 proofs are in separate ML files.
78 HOL contains a theory \isaindexbold{Main}, the union of all the basic
79 predefined theories like arithmetic, lists, sets, etc.
80 Unless you know what you are doing, always include \isa{Main}
81 as a direct or indirect parent of all your theories.
85 \section{Types, Terms and Formulae}
86 \label{sec:TypesTermsForms}
89 Embedded in a theory are the types, terms and formulae of HOL\@. HOL is a typed
90 logic whose type system resembles that of functional programming languages
91 like ML or Haskell. Thus there are
93 \item[base types,] in particular \isaindex{bool}, the type of truth values,
94 and \isaindex{nat}, the type of natural numbers.
95 \item[type constructors,] in particular \isaindex{list}, the type of
96 lists, and \isaindex{set}, the type of sets. Type constructors are written
97 postfix, e.g.\ \isa{(nat)list} is the type of lists whose elements are
98 natural numbers. Parentheses around single arguments can be dropped (as in
99 \isa{nat list}), multiple arguments are separated by commas (as in
101 \item[function types,] denoted by \isasymFun\indexbold{$IsaFun@\isasymFun}.
102 In HOL \isasymFun\ represents \emph{total} functions only. As is customary,
103 \isa{$\tau@1$ \isasymFun~$\tau@2$ \isasymFun~$\tau@3$} means
104 \isa{$\tau@1$ \isasymFun~($\tau@2$ \isasymFun~$\tau@3$)}. Isabelle also
105 supports the notation \isa{[$\tau@1,\dots,\tau@n$] \isasymFun~$\tau$}
106 which abbreviates \isa{$\tau@1$ \isasymFun~$\cdots$ \isasymFun~$\tau@n$
108 \item[type variables,]\indexbold{type variable}\indexbold{variable!type}
109 denoted by \ttindexboldpos{'a}{$Isatype}, \isa{'b} etc., just like in ML\@. They give rise
110 to polymorphic types like \isa{'a \isasymFun~'a}, the type of the identity
114 Types are extremely important because they prevent us from writing
115 nonsense. Isabelle insists that all terms and formulae must be well-typed
116 and will print an error message if a type mismatch is encountered. To
117 reduce the amount of explicit type information that needs to be provided by
118 the user, Isabelle infers the type of all variables automatically (this is
119 called \bfindex{type inference}) and keeps quiet about it. Occasionally
120 this may lead to misunderstandings between you and the system. If anything
121 strange happens, we recommend to set the \rmindex{flag}
122 \isaindexbold{show_types} that tells Isabelle to display type information
123 that is usually suppressed: simply type
129 This can be reversed by \texttt{ML "reset show_types"}. Various other flags,
130 which we introduce as we go along,
131 can be set and reset in the same manner.\indexbold{flag!(re)setting}
135 \textbf{Terms}\indexbold{term} are formed as in functional programming by
136 applying functions to arguments. If \isa{f} is a function of type
137 \isa{$\tau@1$ \isasymFun~$\tau@2$} and \isa{t} is a term of type
138 $\tau@1$ then \isa{f~t} is a term of type $\tau@2$. HOL also supports
139 infix functions like \isa{+} and some basic constructs from functional
142 \item[\isa{if $b$ then $t@1$ else $t@2$}]\indexbold{*if}
143 means what you think it means and requires that
144 $b$ is of type \isa{bool} and $t@1$ and $t@2$ are of the same type.
145 \item[\isa{let $x$ = $t$ in $u$}]\indexbold{*let}
146 is equivalent to $u$ where all occurrences of $x$ have been replaced by
148 \isa{let x = 0 in x+x} is equivalent to \isa{0+0}. Multiple bindings are separated
149 by semicolons: \isa{let $x@1$ = $t@1$; \dots; $x@n$ = $t@n$ in $u$}.
150 \item[\isa{case $e$ of $c@1$ \isasymFun~$e@1$ |~\dots~| $c@n$ \isasymFun~$e@n$}]
152 evaluates to $e@i$ if $e$ is of the form $c@i$.
155 Terms may also contain
156 \isasymlambda-abstractions\indexbold{$Isalam@\isasymlambda}. For example,
157 \isa{\isasymlambda{}x.~x+1} is the function that takes an argument \isa{x} and
158 returns \isa{x+1}. Instead of
159 \isa{\isasymlambda{}x.\isasymlambda{}y.\isasymlambda{}z.~$t$} we can write
160 \isa{\isasymlambda{}x~y~z.~$t$}.
162 \textbf{Formulae}\indexbold{formula} are terms of type \isaindexbold{bool}.
163 There are the basic constants \isaindexbold{True} and \isaindexbold{False} and
164 the usual logical connectives (in decreasing order of priority):
165 \indexboldpos{\isasymnot}{$HOL0not}, \indexboldpos{\isasymand}{$HOL0and},
166 \indexboldpos{\isasymor}{$HOL0or}, and \indexboldpos{\isasymimp}{$HOL0imp},
167 all of which (except the unary \isasymnot) associate to the right. In
168 particular \isa{A \isasymimp~B \isasymimp~C} means \isa{A \isasymimp~(B
169 \isasymimp~C)} and is thus logically equivalent to \isa{A \isasymand~B
170 \isasymimp~C} (which is \isa{(A \isasymand~B) \isasymimp~C}).
172 Equality is available in the form of the infix function
173 \isa{=}\indexbold{$HOL0eq@\texttt{=}} of type \isa{'a \isasymFun~'a
174 \isasymFun~bool}. Thus \isa{$t@1$ = $t@2$} is a formula provided $t@1$
175 and $t@2$ are terms of the same type. In case $t@1$ and $t@2$ are of type
176 \isa{bool}, \isa{=} acts as if-and-only-if. The formula
177 \isa{$t@1$~\isasymnoteq~$t@2$} is merely an abbreviation for
178 \isa{\isasymnot($t@1$ = $t@2$)}.
180 Quantifiers are written as
181 \isa{\isasymforall{}x.~$P$}\indexbold{$HOL0All@\isasymforall} and
182 \isa{\isasymexists{}x.~$P$}\indexbold{$HOL0Ex@\isasymexists}. There is
183 even \isa{\isasymuniqex{}x.~$P$}\index{$HOL0ExU@\isasymuniqex|bold}, which
184 means that there exists exactly one \isa{x} that satisfies \isa{$P$}. Nested
185 quantifications can be abbreviated: \isa{\isasymforall{}x~y~z.~$P$} means
186 \isa{\isasymforall{}x.\isasymforall{}y.\isasymforall{}z.~$P$}.
188 Despite type inference, it is sometimes necessary to attach explicit
189 \textbf{type constraints}\indexbold{type constraint} to a term. The syntax is
190 \isa{$t$::$\tau$} as in \isa{x < (y::nat)}. Note that
191 \ttindexboldpos{::}{$Isatype} binds weakly and should therefore be enclosed
192 in parentheses: \isa{x < y::nat} is ill-typed because it is interpreted as
193 \isa{(x < y)::nat}. The main reason for type constraints is overloading of
194 functions like \isa{+}, \isa{*} and \isa{<}. See {\S}\ref{sec:overloading} for
195 a full discussion of overloading and Table~\ref{tab:overloading} for the most
196 important overloaded function symbols.
199 In general, HOL's concrete syntax tries to follow the conventions of
200 functional programming and mathematics. Below we list the main rules that you
201 should be familiar with to avoid certain syntactic traps. A particular
202 problem for novices can be the priority of operators. If you are unsure, use
203 additional parentheses. In those cases where Isabelle echoes your
204 input, you can see which parentheses are dropped --- they were superfluous. If
205 you are unsure how to interpret Isabelle's output because you don't know
206 where the (dropped) parentheses go, set the \rmindex{flag}
207 \isaindexbold{show_brackets}:
209 ML "set show_brackets"; \(\dots\); ML "reset show_brackets";
215 Remember that \isa{f t u} means \isa{(f t) u} and not \isa{f(t u)}!
217 Isabelle allows infix functions like \isa{+}. The prefix form of function
218 application binds more strongly than anything else and hence \isa{f~x + y}
219 means \isa{(f~x)~+~y} and not \isa{f(x+y)}.
220 \item Remember that in HOL if-and-only-if is expressed using equality. But
221 equality has a high priority, as befitting a relation, while if-and-only-if
222 typically has the lowest priority. Thus, \isa{\isasymnot~\isasymnot~P =
223 P} means \isa{\isasymnot\isasymnot(P = P)} and not
224 \isa{(\isasymnot\isasymnot P) = P}. When using \isa{=} to mean
225 logical equivalence, enclose both operands in parentheses, as in \isa{(A
226 \isasymand~B) = (B \isasymand~A)}.
228 Constructs with an opening but without a closing delimiter bind very weakly
229 and should therefore be enclosed in parentheses if they appear in subterms, as
230 in \isa{(\isasymlambda{}x.~x) = f}. This includes \isaindex{if},
231 \isaindex{let}, \isaindex{case}, \isa{\isasymlambda}, and quantifiers.
233 Never write \isa{\isasymlambda{}x.x} or \isa{\isasymforall{}x.x=x}
234 because \isa{x.x} is always read as a single qualified identifier that
235 refers to an item \isa{x} in theory \isa{x}. Write
236 \isa{\isasymlambda{}x.~x} and \isa{\isasymforall{}x.~x=x} instead.
237 \item Identifiers\indexbold{identifier} may contain \isa{_} and \isa{'}.
240 For the sake of readability the usual mathematical symbols are used throughout
241 the tutorial. Their \textsc{ascii}-equivalents are shown in table~\ref{tab:ascii} in
246 \label{sec:variables}
249 Isabelle distinguishes free and bound variables just as is customary. Bound
250 variables are automatically renamed to avoid clashes with free variables. In
251 addition, Isabelle has a third kind of variable, called a \bfindex{schematic
252 variable}\indexbold{variable!schematic} or \bfindex{unknown}, which starts
253 with a \isa{?}. Logically, an unknown is a free variable. But it may be
254 instantiated by another term during the proof process. For example, the
255 mathematical theorem $x = x$ is represented in Isabelle as \isa{?x = ?x},
256 which means that Isabelle can instantiate it arbitrarily. This is in contrast
257 to ordinary variables, which remain fixed. The programming language Prolog
258 calls unknowns {\em logical\/} variables.
260 Most of the time you can and should ignore unknowns and work with ordinary
261 variables. Just don't be surprised that after you have finished the proof of
262 a theorem, Isabelle will turn your free variables into unknowns: it merely
263 indicates that Isabelle will automatically instantiate those unknowns
264 suitably when the theorem is used in some other proof.
265 Note that for readability we often drop the \isa{?}s when displaying a theorem.
267 If you use \isa{?}\index{$HOL0Ex@\texttt{?}} as an existential
268 quantifier, it needs to be followed by a space. Otherwise \isa{?x} is
269 interpreted as a schematic variable.
272 \section{Interaction and Interfaces}
274 Interaction with Isabelle can either occur at the shell level or through more
275 advanced interfaces. To keep the tutorial independent of the interface we
276 have phrased the description of the intraction in a neutral language. For
277 example, the phrase ``to abandon a proof'' means to type \isacommand{oops} at the
278 shell level, which is explained the first time the phrase is used. Other
279 interfaces perform the same act by cursor movements and/or mouse clicks.
280 Although shell-based interaction is quite feasible for the kind of proof
281 scripts currently presented in this tutorial, the recommended interface for
282 Isabelle/Isar is the Emacs-based \bfindex{Proof
283 General}~\cite{Aspinall:TACAS:2000,proofgeneral}.
285 Some interfaces (including the shell level) offer special fonts with
286 mathematical symbols. For those that do not, remember that \textsc{ascii}-equivalents
287 are shown in table~\ref{tab:ascii} in the appendix.
289 Finally, a word about semicolons.\indexbold{$Isar@\texttt{;}}
290 Commands may but need not be terminated by semicolons.
291 At the shell level it is advisable to use semicolons to enforce that a command
292 is executed immediately; otherwise Isabelle may wait for the next keyword
293 before it knows that the command is complete.
296 \section{Getting Started}
298 Assuming you have installed Isabelle, you start it by typing \texttt{isabelle
299 -I HOL} in a shell window.\footnote{Simply executing \texttt{isabelle -I}
300 starts the default logic, which usually is already \texttt{HOL}. This is
301 controlled by the \texttt{ISABELLE_LOGIC} setting, see \emph{The Isabelle
302 System Manual} for more details.} This presents you with Isabelle's most
303 basic \textsc{ascii} interface. In addition you need to open an editor window to
304 create theory files. While you are developing a theory, we recommend to
305 type each command into the file first and then enter it into Isabelle by
306 copy-and-paste, thus ensuring that you have a complete record of your theory.
307 As mentioned above, Proof General offers a much superior interface.
308 If you have installed Proof General, you can start it by typing \texttt{Isabelle}.