nipkow@8743: \chapter{Basic Concepts}
nipkow@8743: 
nipkow@8743: \section{Introduction}
nipkow@8743: 
nipkow@10971: This is a tutorial on how to use the theorem prover Isabelle/HOL as a specification and
nipkow@8743: verification system. Isabelle is a generic system for implementing logical
nipkow@8743: formalisms, and Isabelle/HOL is the specialization of Isabelle for
nipkow@8743: HOL, which abbreviates Higher-Order Logic. We introduce HOL step by step
nipkow@8743: following the equation
nipkow@8743: \[ \mbox{HOL} = \mbox{Functional Programming} + \mbox{Logic}. \]
nipkow@10983: We do not assume that the reader is familiar with mathematical logic but that
nipkow@11209: (s)he is used to logical and set theoretic notation, such as covered
nipkow@11209: in a good discrete math course~\cite{Rosen-DMA}. In contrast, we do assume
nipkow@11209: that the reader is familiar with the basic concepts of functional
nipkow@11209: programming~\cite{Bird-Haskell,Hudak-Haskell,paulson-ml2,Thompson-Haskell}.
nipkow@11209: Although this tutorial initially concentrates on functional programming, do
nipkow@11209: not be misled: HOL can express most mathematical concepts, and functional
nipkow@11209: programming is just one particularly simple and ubiquitous instance.
nipkow@8743: 
nipkow@11205: Isabelle~\cite{paulson-isa-book} is implemented in ML~\cite{SML}.  This has
nipkow@11205: influenced some of Isabelle/HOL's concrete syntax but is otherwise irrelevant
nipkow@11205: for us because this tutorial is based on
nipkow@11213: Isabelle/Isar~\cite{isabelle-isar-ref}, an extension of Isabelle which hides
nipkow@11213: the implementation language almost completely.  Thus the full name of the
nipkow@11213: system should be Isabelle/Isar/HOL, but that is a bit of a mouthful.
nipkow@11213: 
nipkow@11213: There are other implementations of HOL, in particular the one by Mike Gordon
nipkow@11213: \emph{et al.}, which is usually referred to as ``the HOL system''
nipkow@11213: \cite{mgordon-hol}. For us, HOL refers to the logical system, and sometimes
nipkow@11213: its incarnation Isabelle/HOL.
nipkow@8743: 
nipkow@8743: A tutorial is by definition incomplete.  Currently the tutorial only
nipkow@8743: introduces the rudiments of Isar's proof language. To fully exploit the power
nipkow@11213: of Isar, in particular the ability to write readable and structured proofs,
nipkow@11213: you need to consult the Isabelle/Isar Reference
nipkow@8743: Manual~\cite{isabelle-isar-ref}. If you want to use Isabelle's ML level
nipkow@8743: directly (for example for writing your own proof procedures) see the Isabelle
nipkow@8743: Reference Manual~\cite{isabelle-ref}; for details relating to HOL see the
nipkow@8743: Isabelle/HOL manual~\cite{isabelle-HOL}. All manuals have a comprehensive
nipkow@8743: index.
nipkow@8743: 
nipkow@8743: \section{Theories}
nipkow@8743: \label{sec:Basic:Theories}
nipkow@8743: 
nipkow@8743: Working with Isabelle means creating theories. Roughly speaking, a
nipkow@8743: \bfindex{theory} is a named collection of types, functions, and theorems,
nipkow@8743: much like a module in a programming language or a specification in a
nipkow@8743: specification language. In fact, theories in HOL can be either. The general
nipkow@8743: format of a theory \texttt{T} is
nipkow@8743: \begin{ttbox}
nipkow@8743: theory T = B\(@1\) + \(\cdots\) + B\(@n\):
nipkow@8743: \(\textit{declarations, definitions, and proofs}\)
nipkow@8743: end
nipkow@8743: \end{ttbox}
nipkow@8743: where \texttt{B}$@1$, \dots, \texttt{B}$@n$ are the names of existing
nipkow@8743: theories that \texttt{T} is based on and \texttt{\textit{declarations,
nipkow@8743:     definitions, and proofs}} represents the newly introduced concepts
nipkow@8771: (types, functions etc.) and proofs about them. The \texttt{B}$@i$ are the
nipkow@8743: direct \textbf{parent theories}\indexbold{parent theory} of \texttt{T}.
nipkow@8743: Everything defined in the parent theories (and their parents \dots) is
nipkow@8743: automatically visible. To avoid name clashes, identifiers can be
nipkow@8743: \textbf{qualified} by theory names as in \texttt{T.f} and
nipkow@8743: \texttt{B.f}.\indexbold{identifier!qualified} Each theory \texttt{T} must
nipkow@8771: reside in a \bfindex{theory file} named \texttt{T.thy}.
nipkow@8743: 
nipkow@8743: This tutorial is concerned with introducing you to the different linguistic
nipkow@8743: constructs that can fill \textit{\texttt{declarations, definitions, and
nipkow@8743:     proofs}} in the above theory template.  A complete grammar of the basic
nipkow@8743: constructs is found in the Isabelle/Isar Reference Manual.
nipkow@8743: 
paulson@10885: HOL's theory collection is available online at
nipkow@8743: \begin{center}\small
nipkow@10978:     \url{http://isabelle.in.tum.de/library/HOL/}
nipkow@8743: \end{center}
paulson@10885: and is recommended browsing. Note that most of the theories 
nipkow@9541: are based on classical Isabelle without the Isar extension. This means that
nipkow@9541: they look slightly different than the theories in this tutorial, and that all
nipkow@9541: proofs are in separate ML files.
nipkow@9541: 
nipkow@8743: \begin{warn}
nipkow@9792:   HOL contains a theory \isaindexbold{Main}, the union of all the basic
paulson@10885:   predefined theories like arithmetic, lists, sets, etc.  
paulson@10885:   Unless you know what you are doing, always include \isa{Main}
nipkow@10971:   as a direct or indirect parent of all your theories.
nipkow@8743: \end{warn}
nipkow@8743: 
nipkow@8743: 
paulson@10885: \section{Types, Terms and Formulae}
nipkow@8743: \label{sec:TypesTermsForms}
nipkow@8743: \indexbold{type}
nipkow@8743: 
paulson@10795: Embedded in a theory are the types, terms and formulae of HOL\@. HOL is a typed
nipkow@8771: logic whose type system resembles that of functional programming languages
nipkow@8771: like ML or Haskell. Thus there are
nipkow@8743: \begin{description}
nipkow@8771: \item[base types,] in particular \isaindex{bool}, the type of truth values,
nipkow@8771: and \isaindex{nat}, the type of natural numbers.
nipkow@8771: \item[type constructors,] in particular \isaindex{list}, the type of
nipkow@8771: lists, and \isaindex{set}, the type of sets. Type constructors are written
nipkow@8771: postfix, e.g.\ \isa{(nat)list} is the type of lists whose elements are
nipkow@8743: natural numbers. Parentheses around single arguments can be dropped (as in
nipkow@8771: \isa{nat list}), multiple arguments are separated by commas (as in
nipkow@8771: \isa{(bool,nat)ty}).
nipkow@8743: \item[function types,] denoted by \isasymFun\indexbold{$IsaFun@\isasymFun}.
nipkow@8771:   In HOL \isasymFun\ represents \emph{total} functions only. As is customary,
nipkow@8771:   \isa{$\tau@1$ \isasymFun~$\tau@2$ \isasymFun~$\tau@3$} means
nipkow@8771:   \isa{$\tau@1$ \isasymFun~($\tau@2$ \isasymFun~$\tau@3$)}. Isabelle also
nipkow@8771:   supports the notation \isa{[$\tau@1,\dots,\tau@n$] \isasymFun~$\tau$}
nipkow@8771:   which abbreviates \isa{$\tau@1$ \isasymFun~$\cdots$ \isasymFun~$\tau@n$
nipkow@8743:     \isasymFun~$\tau$}.
nipkow@8771: \item[type variables,]\indexbold{type variable}\indexbold{variable!type}
paulson@10795:   denoted by \ttindexboldpos{'a}{$Isatype}, \isa{'b} etc., just like in ML\@. They give rise
nipkow@8771:   to polymorphic types like \isa{'a \isasymFun~'a}, the type of the identity
nipkow@8771:   function.
nipkow@8743: \end{description}
nipkow@8743: \begin{warn}
nipkow@8743:   Types are extremely important because they prevent us from writing
nipkow@8743:   nonsense.  Isabelle insists that all terms and formulae must be well-typed
nipkow@8743:   and will print an error message if a type mismatch is encountered. To
nipkow@8743:   reduce the amount of explicit type information that needs to be provided by
nipkow@8743:   the user, Isabelle infers the type of all variables automatically (this is
nipkow@8743:   called \bfindex{type inference}) and keeps quiet about it. Occasionally
nipkow@8743:   this may lead to misunderstandings between you and the system. If anything
nipkow@8743:   strange happens, we recommend to set the \rmindex{flag}
nipkow@9792:   \isaindexbold{show_types} that tells Isabelle to display type information
nipkow@8743:   that is usually suppressed: simply type
nipkow@8743: \begin{ttbox}
nipkow@8743: ML "set show_types"
nipkow@8743: \end{ttbox}
nipkow@8743: 
nipkow@8743: \noindent
nipkow@10971: This can be reversed by \texttt{ML "reset show_types"}. Various other flags,
nipkow@10971: which we introduce as we go along,
nipkow@8771: can be set and reset in the same manner.\indexbold{flag!(re)setting}
nipkow@8743: \end{warn}
nipkow@8743: 
nipkow@8743: 
nipkow@8743: \textbf{Terms}\indexbold{term} are formed as in functional programming by
nipkow@8771: applying functions to arguments. If \isa{f} is a function of type
nipkow@8771: \isa{$\tau@1$ \isasymFun~$\tau@2$} and \isa{t} is a term of type
nipkow@8771: $\tau@1$ then \isa{f~t} is a term of type $\tau@2$. HOL also supports
nipkow@8771: infix functions like \isa{+} and some basic constructs from functional
nipkow@8743: programming:
nipkow@8743: \begin{description}
nipkow@8771: \item[\isa{if $b$ then $t@1$ else $t@2$}]\indexbold{*if}
nipkow@8743: means what you think it means and requires that
nipkow@8771: $b$ is of type \isa{bool} and $t@1$ and $t@2$ are of the same type.
nipkow@8771: \item[\isa{let $x$ = $t$ in $u$}]\indexbold{*let}
nipkow@8743: is equivalent to $u$ where all occurrences of $x$ have been replaced by
nipkow@8743: $t$. For example,
nipkow@8771: \isa{let x = 0 in x+x} is equivalent to \isa{0+0}. Multiple bindings are separated
nipkow@8771: by semicolons: \isa{let $x@1$ = $t@1$; \dots; $x@n$ = $t@n$ in $u$}.
nipkow@8771: \item[\isa{case $e$ of $c@1$ \isasymFun~$e@1$ |~\dots~| $c@n$ \isasymFun~$e@n$}]
nipkow@8743: \indexbold{*case}
nipkow@8771: evaluates to $e@i$ if $e$ is of the form $c@i$.
nipkow@8743: \end{description}
nipkow@8743: 
nipkow@8743: Terms may also contain
nipkow@8743: \isasymlambda-abstractions\indexbold{$Isalam@\isasymlambda}. For example,
nipkow@8771: \isa{\isasymlambda{}x.~x+1} is the function that takes an argument \isa{x} and
nipkow@8771: returns \isa{x+1}. Instead of
nipkow@8771: \isa{\isasymlambda{}x.\isasymlambda{}y.\isasymlambda{}z.~$t$} we can write
nipkow@8771: \isa{\isasymlambda{}x~y~z.~$t$}.
nipkow@8743: 
nipkow@8771: \textbf{Formulae}\indexbold{formula} are terms of type \isaindexbold{bool}.
nipkow@8771: There are the basic constants \isaindexbold{True} and \isaindexbold{False} and
nipkow@8771: the usual logical connectives (in decreasing order of priority):
nipkow@8771: \indexboldpos{\isasymnot}{$HOL0not}, \indexboldpos{\isasymand}{$HOL0and},
nipkow@8771: \indexboldpos{\isasymor}{$HOL0or}, and \indexboldpos{\isasymimp}{$HOL0imp},
nipkow@8743: all of which (except the unary \isasymnot) associate to the right. In
nipkow@8771: particular \isa{A \isasymimp~B \isasymimp~C} means \isa{A \isasymimp~(B
nipkow@8771:   \isasymimp~C)} and is thus logically equivalent to \isa{A \isasymand~B
nipkow@8771:   \isasymimp~C} (which is \isa{(A \isasymand~B) \isasymimp~C}).
nipkow@8743: 
nipkow@8743: Equality is available in the form of the infix function
nipkow@8771: \isa{=}\indexbold{$HOL0eq@\texttt{=}} of type \isa{'a \isasymFun~'a
nipkow@8771:   \isasymFun~bool}. Thus \isa{$t@1$ = $t@2$} is a formula provided $t@1$
nipkow@8743: and $t@2$ are terms of the same type. In case $t@1$ and $t@2$ are of type
nipkow@8771: \isa{bool}, \isa{=} acts as if-and-only-if. The formula
nipkow@8771: \isa{$t@1$~\isasymnoteq~$t@2$} is merely an abbreviation for
nipkow@8771: \isa{\isasymnot($t@1$ = $t@2$)}.
nipkow@8743: 
paulson@10795: Quantifiers are written as
nipkow@8771: \isa{\isasymforall{}x.~$P$}\indexbold{$HOL0All@\isasymforall} and
nipkow@8771: \isa{\isasymexists{}x.~$P$}\indexbold{$HOL0Ex@\isasymexists}.  There is
nipkow@8771: even \isa{\isasymuniqex{}x.~$P$}\index{$HOL0ExU@\isasymuniqex|bold}, which
nipkow@8771: means that there exists exactly one \isa{x} that satisfies \isa{$P$}.  Nested
nipkow@8771: quantifications can be abbreviated: \isa{\isasymforall{}x~y~z.~$P$} means
nipkow@8771: \isa{\isasymforall{}x.\isasymforall{}y.\isasymforall{}z.~$P$}.
nipkow@8743: 
nipkow@8743: Despite type inference, it is sometimes necessary to attach explicit
nipkow@8771: \textbf{type constraints}\indexbold{type constraint} to a term.  The syntax is
nipkow@8771: \isa{$t$::$\tau$} as in \isa{x < (y::nat)}. Note that
nipkow@10538: \ttindexboldpos{::}{$Isatype} binds weakly and should therefore be enclosed
nipkow@8771: in parentheses: \isa{x < y::nat} is ill-typed because it is interpreted as
paulson@10795: \isa{(x < y)::nat}. The main reason for type constraints is overloading of
nipkow@10538: functions like \isa{+}, \isa{*} and \isa{<}. See {\S}\ref{sec:overloading} for
nipkow@10695: a full discussion of overloading and Table~\ref{tab:overloading} for the most
nipkow@10695: important overloaded function symbols.
nipkow@8743: 
nipkow@8743: \begin{warn}
nipkow@8743: In general, HOL's concrete syntax tries to follow the conventions of
nipkow@8743: functional programming and mathematics. Below we list the main rules that you
nipkow@8743: should be familiar with to avoid certain syntactic traps. A particular
nipkow@8743: problem for novices can be the priority of operators. If you are unsure, use
paulson@10795: additional parentheses. In those cases where Isabelle echoes your
nipkow@10971: input, you can see which parentheses are dropped --- they were superfluous. If
nipkow@8743: you are unsure how to interpret Isabelle's output because you don't know
paulson@10795: where the (dropped) parentheses go, set the \rmindex{flag}
nipkow@9792: \isaindexbold{show_brackets}:
nipkow@8743: \begin{ttbox}
nipkow@8743: ML "set show_brackets"; \(\dots\); ML "reset show_brackets";
nipkow@8743: \end{ttbox}
nipkow@8743: \end{warn}
nipkow@8743: 
nipkow@8743: \begin{itemize}
nipkow@8743: \item
nipkow@8771: Remember that \isa{f t u} means \isa{(f t) u} and not \isa{f(t u)}!
nipkow@8743: \item
nipkow@8771: Isabelle allows infix functions like \isa{+}. The prefix form of function
nipkow@8771: application binds more strongly than anything else and hence \isa{f~x + y}
nipkow@8771: means \isa{(f~x)~+~y} and not \isa{f(x+y)}.
nipkow@8743: \item Remember that in HOL if-and-only-if is expressed using equality.  But
nipkow@8743:   equality has a high priority, as befitting a relation, while if-and-only-if
nipkow@8771:   typically has the lowest priority.  Thus, \isa{\isasymnot~\isasymnot~P =
nipkow@8771:     P} means \isa{\isasymnot\isasymnot(P = P)} and not
nipkow@8771:   \isa{(\isasymnot\isasymnot P) = P}. When using \isa{=} to mean
nipkow@8771:   logical equivalence, enclose both operands in parentheses, as in \isa{(A
nipkow@8743:     \isasymand~B) = (B \isasymand~A)}.
nipkow@8743: \item
nipkow@8743: Constructs with an opening but without a closing delimiter bind very weakly
nipkow@8743: and should therefore be enclosed in parentheses if they appear in subterms, as
nipkow@10971: in \isa{(\isasymlambda{}x.~x) = f}. This includes \isaindex{if},
nipkow@8771: \isaindex{let}, \isaindex{case}, \isa{\isasymlambda}, and quantifiers.
nipkow@8743: \item
nipkow@8771: Never write \isa{\isasymlambda{}x.x} or \isa{\isasymforall{}x.x=x}
nipkow@8771: because \isa{x.x} is always read as a single qualified identifier that
nipkow@8771: refers to an item \isa{x} in theory \isa{x}. Write
nipkow@8771: \isa{\isasymlambda{}x.~x} and \isa{\isasymforall{}x.~x=x} instead.
nipkow@8771: \item Identifiers\indexbold{identifier} may contain \isa{_} and \isa{'}.
nipkow@8743: \end{itemize}
nipkow@8743: 
nipkow@8771: For the sake of readability the usual mathematical symbols are used throughout
nipkow@10983: the tutorial. Their \textsc{ascii}-equivalents are shown in table~\ref{tab:ascii} in
nipkow@8771: the appendix.
nipkow@8771: 
nipkow@8743: 
nipkow@8743: \section{Variables}
nipkow@8743: \label{sec:variables}
nipkow@8743: \indexbold{variable}
nipkow@8743: 
nipkow@8743: Isabelle distinguishes free and bound variables just as is customary. Bound
nipkow@8743: variables are automatically renamed to avoid clashes with free variables. In
nipkow@8743: addition, Isabelle has a third kind of variable, called a \bfindex{schematic
nipkow@8743:   variable}\indexbold{variable!schematic} or \bfindex{unknown}, which starts
nipkow@8771: with a \isa{?}.  Logically, an unknown is a free variable. But it may be
nipkow@8743: instantiated by another term during the proof process. For example, the
nipkow@8771: mathematical theorem $x = x$ is represented in Isabelle as \isa{?x = ?x},
nipkow@8743: which means that Isabelle can instantiate it arbitrarily. This is in contrast
nipkow@8743: to ordinary variables, which remain fixed. The programming language Prolog
nipkow@8743: calls unknowns {\em logical\/} variables.
nipkow@8743: 
nipkow@8743: Most of the time you can and should ignore unknowns and work with ordinary
nipkow@8743: variables. Just don't be surprised that after you have finished the proof of
nipkow@8743: a theorem, Isabelle will turn your free variables into unknowns: it merely
nipkow@8743: indicates that Isabelle will automatically instantiate those unknowns
nipkow@8743: suitably when the theorem is used in some other proof.
nipkow@9689: Note that for readability we often drop the \isa{?}s when displaying a theorem.
nipkow@8743: \begin{warn}
nipkow@8771:   If you use \isa{?}\index{$HOL0Ex@\texttt{?}} as an existential
nipkow@8771:   quantifier, it needs to be followed by a space. Otherwise \isa{?x} is
nipkow@8743:   interpreted as a schematic variable.
nipkow@8743: \end{warn}
nipkow@8743: 
paulson@10885: \section{Interaction and Interfaces}
nipkow@8771: 
nipkow@8771: Interaction with Isabelle can either occur at the shell level or through more
nipkow@8771: advanced interfaces. To keep the tutorial independent of the interface we
nipkow@8771: have phrased the description of the intraction in a neutral language. For
nipkow@8771: example, the phrase ``to abandon a proof'' means to type \isacommand{oops} at the
nipkow@8771: shell level, which is explained the first time the phrase is used. Other
nipkow@8771: interfaces perform the same act by cursor movements and/or mouse clicks.
nipkow@8771: Although shell-based interaction is quite feasible for the kind of proof
nipkow@8771: scripts currently presented in this tutorial, the recommended interface for
nipkow@8771: Isabelle/Isar is the Emacs-based \bfindex{Proof
nipkow@8771:   General}~\cite{Aspinall:TACAS:2000,proofgeneral}.
nipkow@8771: 
nipkow@8771: Some interfaces (including the shell level) offer special fonts with
nipkow@10983: mathematical symbols. For those that do not, remember that \textsc{ascii}-equivalents
nipkow@10978: are shown in table~\ref{tab:ascii} in the appendix.
nipkow@8771: 
nipkow@9541: Finally, a word about semicolons.\indexbold{$Isar@\texttt{;}} 
nipkow@9541: Commands may but need not be terminated by semicolons.
nipkow@9541: At the shell level it is advisable to use semicolons to enforce that a command
nipkow@8771: is executed immediately; otherwise Isabelle may wait for the next keyword
nipkow@9541: before it knows that the command is complete.
nipkow@8771: 
nipkow@8771: 
paulson@10885: \section{Getting Started}
nipkow@8743: 
nipkow@8743: Assuming you have installed Isabelle, you start it by typing \texttt{isabelle
nipkow@8743:   -I HOL} in a shell window.\footnote{Simply executing \texttt{isabelle -I}
nipkow@8743:   starts the default logic, which usually is already \texttt{HOL}.  This is
nipkow@8743:   controlled by the \texttt{ISABELLE_LOGIC} setting, see \emph{The Isabelle
nipkow@8743:     System Manual} for more details.} This presents you with Isabelle's most
nipkow@10983: basic \textsc{ascii} interface.  In addition you need to open an editor window to
nipkow@8743: create theory files.  While you are developing a theory, we recommend to
nipkow@8743: type each command into the file first and then enter it into Isabelle by
nipkow@8743: copy-and-paste, thus ensuring that you have a complete record of your theory.
nipkow@8771: As mentioned above, Proof General offers a much superior interface.
paulson@10795: If you have installed Proof General, you can start it by typing \texttt{Isabelle}.