%

\begin{isabellebody}%

\def\isabellecontext{ToyList}%

\isacommand{theory}\ ToyList\ {\isacharequal}\ PreList{\isacharcolon}%

\begin{isamarkuptext}%

\noindent

HOL already has a predefined theory of lists called \isa{List} ---

\isa{ToyList} is merely a small fragment of it chosen as an example. In

contrast to what is recommended in \S\ref{sec:Basic:Theories},

\isa{ToyList} is not based on \isa{Main} but on \isa{PreList}, a

theory that contains pretty much everything but lists, thus avoiding

ambiguities caused by defining lists twice.%

\end{isamarkuptext}%

\isacommand{datatype}\ {\isacharprime}a\ list\ {\isacharequal}\ Nil\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isacharparenleft}{\isachardoublequote}{\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}{\isacharparenright}\isanewline

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isacharbar}\ Cons\ {\isacharprime}a\ {\isachardoublequote}{\isacharprime}a\ list{\isachardoublequote}\ \ \ \ \ \ \ \ \ \ \ \ {\isacharparenleft}\isakeyword{infixr}\ {\isachardoublequote}{\isacharhash}{\isachardoublequote}\ \isadigit{6}\isadigit{5}{\isacharparenright}%

\begin{isamarkuptext}%

\noindent

The datatype\index{*datatype} \isaindexbold{list} introduces two

constructors \isaindexbold{Nil} and \isaindexbold{Cons}, the

empty~list and the operator that adds an element to the front of a list. For

example, the term \isa{Cons True (Cons False Nil)} is a value of

type \isa{bool\ list}, namely the list with the elements \isa{True} and

\isa{False}. Because this notation becomes unwieldy very quickly, the

datatype declaration is annotated with an alternative syntax: instead of

\isa{Nil} and \isa{Cons x xs} we can write

\isa{{\isacharbrackleft}{\isacharbrackright}}\index{$HOL2list@\texttt{[]}|bold} and

\isa{x\ {\isacharhash}\ xs}\index{$HOL2list@\texttt{\#}|bold}. In fact, this

alternative syntax is the standard syntax. Thus the list \isa{Cons True

(Cons False Nil)} becomes \isa{True\ {\isacharhash}\ False\ {\isacharhash}\ {\isacharbrackleft}{\isacharbrackright}}. The annotation

\isacommand{infixr}\indexbold{*infixr} means that \isa{{\isacharhash}} associates to

the right, i.e.\ the term \isa{x\ {\isacharhash}\ y\ {\isacharhash}\ z} is read as \isa{x\ {\isacharhash}\ {\isacharparenleft}y\ {\isacharhash}\ z{\isacharparenright}}

and not as \isa{{\isacharparenleft}x\ {\isacharhash}\ y{\isacharparenright}\ {\isacharhash}\ z}.

\begin{warn}

  Syntax annotations are a powerful but completely optional feature. You

  could drop them from theory \isa{ToyList} and go back to the identifiers

  \isa{Nil} and \isa{Cons}. However, lists are such a

  central datatype

  that their syntax is highly customized. We recommend that novices should

  not use syntax annotations in their own theories.

\end{warn}

Next, two functions \isa{app} and \isaindexbold{rev} are declared:%

\end{isamarkuptext}%

\isacommand{consts}\ app\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}\ \ \ {\isacharparenleft}\isakeyword{infixr}\ {\isachardoublequote}{\isacharat}{\isachardoublequote}\ \isadigit{6}\isadigit{5}{\isacharparenright}\isanewline

\ \ \ \ \ \ \ rev\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequote}%

\begin{isamarkuptext}%

\noindent

In contrast to ML, Isabelle insists on explicit declarations of all functions

(keyword \isacommand{consts}).  (Apart from the declaration-before-use

restriction, the order of items in a theory file is unconstrained.) Function

\isa{op\ {\isacharat}} is annotated with concrete syntax too. Instead of the prefix

syntax \isa{app xs ys} the infix

\isa{xs\ {\isacharat}\ ys}\index{$HOL2list@\texttt{\at}|bold} becomes the preferred

form. Both functions are defined recursively:%

\end{isamarkuptext}%

\isacommand{primrec}\isanewline

{\isachardoublequote}{\isacharbrackleft}{\isacharbrackright}\ {\isacharat}\ ys\ \ \ \ \ \ \ {\isacharequal}\ ys{\isachardoublequote}\isanewline

{\isachardoublequote}{\isacharparenleft}x\ {\isacharhash}\ xs{\isacharparenright}\ {\isacharat}\ ys\ {\isacharequal}\ x\ {\isacharhash}\ {\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}{\isachardoublequote}\isanewline

\isanewline

\isacommand{primrec}\isanewline

{\isachardoublequote}rev\ {\isacharbrackleft}{\isacharbrackright}\ \ \ \ \ \ \ \ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline

{\isachardoublequote}rev\ {\isacharparenleft}x\ {\isacharhash}\ xs{\isacharparenright}\ \ {\isacharequal}\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}x\ {\isacharhash}\ {\isacharbrackleft}{\isacharbrackright}{\isacharparenright}{\isachardoublequote}%

\begin{isamarkuptext}%

\noindent

The equations for \isa{op\ {\isacharat}} and \isa{rev} hardly need comments:

\isa{op\ {\isacharat}} appends two lists and \isa{rev} reverses a list.  The keyword

\isacommand{primrec}\index{*primrec} indicates that the recursion is of a

particularly primitive kind where each recursive call peels off a datatype

constructor from one of the arguments.  Thus the

recursion always terminates, i.e.\ the function is \bfindex{total}.

The termination requirement is absolutely essential in HOL, a logic of total

functions. If we were to drop it, inconsistencies would quickly arise: the

``definition'' $f(n) = f(n)+1$ immediately leads to $0 = 1$ by subtracting

$f(n)$ on both sides.

% However, this is a subtle issue that we cannot discuss here further.

\begin{warn}

  As we have indicated, the desire for total functions is not a gratuitously

  imposed restriction but an essential characteristic of HOL. It is only

  because of totality that reasoning in HOL is comparatively easy.  More

  generally, the philosophy in HOL is not to allow arbitrary axioms (such as

  function definitions whose totality has not been proved) because they

  quickly lead to inconsistencies. Instead, fixed constructs for introducing

  types and functions are offered (such as \isacommand{datatype} and

  \isacommand{primrec}) which are guaranteed to preserve consistency.

\end{warn}

A remark about syntax.  The textual definition of a theory follows a fixed

syntax with keywords like \isacommand{datatype} and \isacommand{end} (see

Fig.~\ref{fig:keywords} in Appendix~\ref{sec:Appendix} for a full list).

Embedded in this syntax are the types and formulae of HOL, whose syntax is

extensible, e.g.\ by new user-defined infix operators

(see~\ref{sec:infix-syntax}). To distinguish the two levels, everything

HOL-specific (terms and types) should be enclosed in

\texttt{"}\dots\texttt{"}. 

To lessen this burden, quotation marks around a single identifier can be

dropped, unless the identifier happens to be a keyword, as in%

\end{isamarkuptext}%

\isacommand{consts}\ {\isachardoublequote}end{\isachardoublequote}\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a{\isachardoublequote}%

\begin{isamarkuptext}%

\noindent

When Isabelle prints a syntax error message, it refers to the HOL syntax as

the \bfindex{inner syntax} and the enclosing theory language as the \bfindex{outer syntax}.

\section{An introductory proof}

\label{sec:intro-proof}

Assuming you have input the declarations and definitions of \texttt{ToyList}

presented so far, we are ready to prove a few simple theorems. This will

illustrate not just the basic proof commands but also the typical proof

process.

\subsubsection*{Main goal: \isa{rev{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs}}

Our goal is to show that reversing a list twice produces the original

list. The input line%

\end{isamarkuptext}%

\isacommand{theorem}\ rev{\isacharunderscore}rev\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs{\isachardoublequote}%

\begin{isamarkuptxt}%

\index{*theorem|bold}\index{*simp (attribute)|bold}

\begin{itemize}

\item

establishes a new theorem to be proved, namely \isa{rev\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs},

\item

gives that theorem the name \isa{rev{\isacharunderscore}rev} by which it can be

referred to,

\item

and tells Isabelle (via \isa{{\isacharbrackleft}simp{\isacharbrackright}}) to use the theorem (once it has been

proved) as a simplification rule, i.e.\ all future proofs involving

simplification will replace occurrences of \isa{rev\ {\isacharparenleft}rev\ xs{\isacharparenright}} by

\isa{xs}.

The name and the simplification attribute are optional.

\end{itemize}

Isabelle's response is to print

\begin{isabelle}

proof(prove):~step~0\isanewline

\isanewline

goal~(theorem~rev\_rev):\isanewline

rev~(rev~xs)~=~xs\isanewline

~1.~rev~(rev~xs)~=~xs

\end{isabelle}

The first three lines tell us that we are 0 steps into the proof of

theorem \isa{rev{\isacharunderscore}rev}; for compactness reasons we rarely show these

initial lines in this tutorial. The remaining lines display the current

proof state.

Until we have finished a proof, the proof state always looks like this:

\begin{isabelle}

$G$\isanewline

~1.~$G\sb{1}$\isanewline

~~\vdots~~\isanewline

~$n$.~$G\sb{n}$

\end{isabelle}

where $G$

is the overall goal that we are trying to prove, and the numbered lines

contain the subgoals $G\sb{1}$, \dots, $G\sb{n}$ that we need to prove to

establish $G$. At \isa{step\ \isadigit{0}} there is only one subgoal, which is

identical with the overall goal.  Normally $G$ is constant and only serves as

a reminder. Hence we rarely show it in this tutorial.

Let us now get back to \isa{rev\ {\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs}. Properties of recursively

defined functions are best established by induction. In this case there is

not much choice except to induct on \isa{xs}:%

\end{isamarkuptxt}%

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}%

\begin{isamarkuptxt}%

\noindent\index{*induct_tac}%

This tells Isabelle to perform induction on variable \isa{xs}. The suffix

\isa{tac} stands for ``tactic'', a synonym for ``theorem proving function''.

By default, induction acts on the first subgoal. The new proof state contains

two subgoals, namely the base case (\isa{Nil}) and the induction step

(\isa{Cons}):

\begin{isabelle}

~1.~rev~(rev~[])~=~[]\isanewline

~2.~{\isasymAnd}a~list.~rev(rev~list)~=~list~{\isasymLongrightarrow}~rev(rev(a~\#~list))~=~a~\#~list

\end{isabelle}

The induction step is an example of the general format of a subgoal:

\begin{isabelle}

~$i$.~{\indexboldpos{\isasymAnd}{$IsaAnd}}$x\sb{1}$~\dots~$x\sb{n}$.~{\it assumptions}~{\isasymLongrightarrow}~{\it conclusion}

\end{isabelle}

The prefix of bound variables \isasymAnd$x\sb{1}$~\dots~$x\sb{n}$ can be

ignored most of the time, or simply treated as a list of variables local to

this subgoal. Their deeper significance is explained in \S\ref{sec:PCproofs}.

The {\it assumptions} are the local assumptions for this subgoal and {\it

  conclusion} is the actual proposition to be proved. Typical proof steps

that add new assumptions are induction or case distinction. In our example

the only assumption is the induction hypothesis \isa{rev\ {\isacharparenleft}rev\ list{\isacharparenright}\ {\isacharequal}\ list}, where \isa{list} is a variable name chosen by Isabelle. If there

are multiple assumptions, they are enclosed in the bracket pair

\indexboldpos{\isasymlbrakk}{$Isabrl} and

\indexboldpos{\isasymrbrakk}{$Isabrr} and separated by semicolons.

Let us try to solve both goals automatically:%

\end{isamarkuptxt}%

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}%

\begin{isamarkuptxt}%

\noindent

This command tells Isabelle to apply a proof strategy called

\isa{auto} to all subgoals. Essentially, \isa{auto} tries to

``simplify'' the subgoals.  In our case, subgoal~1 is solved completely (thanks

to the equation \isa{rev\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}) and disappears; the simplified version

of subgoal~2 becomes the new subgoal~1:

\begin{isabelle}

~1.~\dots~rev(rev~list)~=~list~{\isasymLongrightarrow}~rev(rev~list~@~a~\#~[])~=~a~\#~list

\end{isabelle}

In order to simplify this subgoal further, a lemma suggests itself.%

\end{isamarkuptxt}%

%

\isamarkupsubsubsection{First lemma: \isa{rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}}}

%

\begin{isamarkuptext}%

After abandoning the above proof attempt\indexbold{abandon

proof}\indexbold{proof!abandon} (at the shell level type

\isacommand{oops}\indexbold{*oops}) we start a new proof:%

\end{isamarkuptext}%

\isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}%

\begin{isamarkuptxt}%

\noindent The keywords \isacommand{theorem}\index{*theorem} and

\isacommand{lemma}\indexbold{*lemma} are interchangable and merely indicate

the importance we attach to a proposition. In general, we use the words

\emph{theorem}\index{theorem} and \emph{lemma}\index{lemma} pretty much

interchangeably.

There are two variables that we could induct on: \isa{xs} and

\isa{ys}. Because \isa{{\isacharat}} is defined by recursion on

the first argument, \isa{xs} is the correct one:%

\end{isamarkuptxt}%

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}%

\begin{isamarkuptxt}%

\noindent

This time not even the base case is solved automatically:%

\end{isamarkuptxt}%

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}%

\begin{isamarkuptxt}%

\begin{isabelle}

~1.~rev~ys~=~rev~ys~@~[]\isanewline

~2. \dots

\end{isabelle}

Again, we need to abandon this proof attempt and prove another simple lemma first.

In the future the step of abandoning an incomplete proof before embarking on

the proof of a lemma usually remains implicit.%

\end{isamarkuptxt}%

%

\isamarkupsubsubsection{Second lemma: \isa{xs\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ xs}}

%

\begin{isamarkuptext}%

This time the canonical proof procedure%

\end{isamarkuptext}%

\isacommand{lemma}\ app{\isacharunderscore}Nil\isadigit{2}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}xs\ {\isacharat}\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ xs{\isachardoublequote}\isanewline

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}%

\begin{isamarkuptxt}%

\noindent

leads to the desired message \isa{No\ subgoals{\isacharbang}}:

\begin{isabelle}

xs~@~[]~=~xs\isanewline

No~subgoals!

\end{isabelle}

We still need to confirm that the proof is now finished:%

\end{isamarkuptxt}%

\isacommand{done}%

\begin{isamarkuptext}%

\noindent\indexbold{done}%

As a result of that final \isacommand{done}, Isabelle associates the lemma just proved

with its name. In this tutorial, we sometimes omit to show that final \isacommand{done}

if it is obvious from the context that the proof is finished.

% Instead of \isacommand{apply} followed by a dot, you can simply write

% \isacommand{by}\indexbold{by}, which we do most of the time.

Notice that in lemma \isa{app{\isacharunderscore}Nil\isadigit{2}}

(as printed out after the final \isacommand{done}) the free variable \isa{xs} has been

replaced by the unknown \isa{{\isacharquery}xs}, just as explained in

\S\ref{sec:variables}.

Going back to the proof of the first lemma%

\end{isamarkuptext}%

\isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isanewline

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}%

\begin{isamarkuptxt}%

\noindent

we find that this time \isa{auto} solves the base case, but the

induction step merely simplifies to

\begin{isabelle}

~1.~{\isasymAnd}a~list.\isanewline

~~~~~~~rev~(list~@~ys)~=~rev~ys~@~rev~list~{\isasymLongrightarrow}\isanewline

~~~~~~~(rev~ys~@~rev~list)~@~a~\#~[]~=~rev~ys~@~rev~list~@~a~\#~[]

\end{isabelle}

Now we need to remember that \isa{{\isacharat}} associates to the right, and that

\isa{{\isacharhash}} and \isa{{\isacharat}} have the same priority (namely the \isa{\isadigit{6}\isadigit{5}}

in their \isacommand{infixr} annotation). Thus the conclusion really is

\begin{isabelle}

~~~~~(rev~ys~@~rev~list)~@~(a~\#~[])~=~rev~ys~@~(rev~list~@~(a~\#~[]))

\end{isabelle}

and the missing lemma is associativity of \isa{{\isacharat}}.%

\end{isamarkuptxt}%

%

\isamarkupsubsubsection{Third lemma: \isa{{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ {\isacharparenleft}ys\ {\isacharat}\ zs{\isacharparenright}}}

%

\begin{isamarkuptext}%

Abandoning the previous proof, the canonical proof procedure%

\end{isamarkuptext}%

\isacommand{lemma}\ app{\isacharunderscore}assoc\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharat}\ zs\ {\isacharequal}\ xs\ {\isacharat}\ {\isacharparenleft}ys\ {\isacharat}\ zs{\isacharparenright}{\isachardoublequote}\isanewline

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isanewline

\isacommand{done}%

\begin{isamarkuptext}%

\noindent

succeeds without further ado.

Now we can go back and prove the first lemma%

\end{isamarkuptext}%

\isacommand{lemma}\ rev{\isacharunderscore}app\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}xs\ {\isacharat}\ ys{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}rev\ ys{\isacharparenright}\ {\isacharat}\ {\isacharparenleft}rev\ xs{\isacharparenright}{\isachardoublequote}\isanewline

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isanewline

\isacommand{done}%

\begin{isamarkuptext}%

\noindent

and then solve our main theorem:%

\end{isamarkuptext}%

\isacommand{theorem}\ rev{\isacharunderscore}rev\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}rev{\isacharparenleft}rev\ xs{\isacharparenright}\ {\isacharequal}\ xs{\isachardoublequote}\isanewline

\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ xs{\isacharparenright}\isanewline

\isacommand{apply}{\isacharparenleft}auto{\isacharparenright}\isanewline

\isacommand{done}%

\begin{isamarkuptext}%

\noindent

The final \isacommand{end} tells Isabelle to close the current theory because

we are finished with its development:%

\end{isamarkuptext}%

\isacommand{end}\isanewline

\end{isabellebody}%

%%% Local Variables:

%%% mode: latex

%%% TeX-master: "root"

%%% End: