1 \section{Introduction} |
1 \section{Introduction} |
2 |
2 |
3 Isabelle is a generic proof assistant. Isar is an extension of |
3 This is a tutorial introduction to structured proofs in Isabelle/HOL. |
4 Isabelle with structured proofs in a stylised language of mathematics. |
4 It introduces the core of the proof language Isar by example. Isar is |
5 These proofs are readable for both a human and a machine. |
5 an extension of the \isa{apply}-style proofs introduced in the |
6 Isabelle/HOL~\cite{LNCS2283} is a specialisation of Isabelle with |
6 Isabelle/HOL tutorial~\cite{LNCS2283} with structured proofs in a |
7 higher-order logic (HOL). This paper is a compact introduction to |
7 stylised language of mathematics. These proofs are readable for both |
8 structured proofs in Isar/HOL, an extension of Isabelle/HOL. We |
8 human and machine. |
9 intentionally do not present the full language but concentrate on the |
|
10 essentials. Neither do we give a formal semantics of Isar. Instead we |
|
11 introduce Isar by example. We believe that the language ``speaks for |
|
12 itself'' in the same way that traditional mathematical proofs do, |
|
13 which are also introduced by example rather than by teaching students |
|
14 logic first. A detailed exposition of Isar can be found in Markus |
|
15 Wenzel's PhD thesis~\cite{Wenzel-PhD} (which also discusses related |
|
16 work) and the Isar reference manual~\cite{Isar-Ref-Man}. |
|
17 |
|
18 \subsection{Background} |
|
19 |
|
20 Interactive theorem proving has been dominated by a model of proof |
|
21 that goes back to the LCF system~\cite{LCF}: a proof is a more or less |
|
22 structured sequence of commands that manipulate an implicit proof |
|
23 state. Thus the proof text is only suitable for the machine; for a |
|
24 human, the proof only comes alive when he can see the state changes |
|
25 caused by the stepwise execution of the commands. Such proofs are like |
|
26 uncommented assembly language programs. We call them |
|
27 \emph{tactic-style} proofs because LCF proof commands were called |
|
28 tactics. |
|
29 |
|
30 A radically different approach was taken by the Mizar |
|
31 system~\cite{Rudnicki92} where proofs are written in a stylised language akin |
|
32 to that used in ordinary mathematics texts. The most important argument in |
|
33 favour of a mathematics-like proof language is communication: as soon as not |
|
34 just the theorem but also the proof becomes an object of interest, it should |
|
35 be readable. From a system development point of view there is a second |
|
36 important argument against tactic-style proofs: they are much harder to |
|
37 maintain when the system is modified. |
|
38 %The reason is as follows. Since it is |
|
39 %usually quite unclear what exactly is proved at some point in the middle of a |
|
40 %command sequence, updating a failed proof often requires executing the proof |
|
41 %up to the point of failure using the old version of the system. In contrast, |
|
42 %mathematics-like proofs contain enough information to tell you what is proved |
|
43 %at any point. |
|
44 |
|
45 For these reasons the Isabelle system, originally firmly in the |
|
46 LCF-tradition, was extended with a language for writing structured |
|
47 proofs in a mathematics-like style. As the name already indicates, |
|
48 Isar was certainly inspired by Mizar. However, there are many |
|
49 differences. For a start, Isar is generic: only a few of the language |
|
50 constructs described below are specific to HOL; many are generic and |
|
51 thus available for any logic defined in Isabelle, e.g.\ ZF. |
|
52 Furthermore, we have Isabelle's powerful automatic proof procedures at |
|
53 our disposal. A closer comparison of Isar and Mizar can be found |
|
54 elsewhere~\cite{WenzelW-JAR}. |
|
55 |
9 |
56 \subsection{A first glimpse of Isar} |
10 \subsection{A first glimpse of Isar} |
57 Below you find a simplified grammar for Isar proofs. |
11 Below you find a simplified grammar for Isar proofs. |
58 Parentheses are used for grouping and $^?$ indicates an optional item: |
12 Parentheses are used for grouping and $^?$ indicates an optional item: |
59 \begin{center} |
13 \begin{center} |
62 \emph{statement}* |
16 \emph{statement}* |
63 \isakeyword{qed} \\ |
17 \isakeyword{qed} \\ |
64 &$\mid$& \isakeyword{by} \emph{method}\\[1ex] |
18 &$\mid$& \isakeyword{by} \emph{method}\\[1ex] |
65 \emph{statement} &::= & \isakeyword{fix} \emph{variables} \\ |
19 \emph{statement} &::= & \isakeyword{fix} \emph{variables} \\ |
66 &$\mid$& \isakeyword{assume} \emph{propositions} \\ |
20 &$\mid$& \isakeyword{assume} \emph{propositions} \\ |
67 &$\mid$& (\isakeyword{from} \emph{facts})$^?$ |
21 &$\mid$& (\isakeyword{from} \emph{fact}*)$^?$ |
68 (\isakeyword{show} $\mid$ \isakeyword{have}) |
22 (\isakeyword{show} $\mid$ \isakeyword{have}) |
69 \emph{propositions} \emph{proof} \\[1ex] |
23 \emph{propositions} \emph{proof} \\[1ex] |
70 \emph{proposition} &::=& (\emph{label}{\bf:})$^?$ \emph{string} \\[1ex] |
24 \emph{proposition} &::=& (\emph{label}{\bf:})$^?$ \emph{string} \\[1ex] |
71 \emph{fact} &::=& \emph{label} |
25 \emph{fact} &::=& \emph{label} |
72 \end{tabular} |
26 \end{tabular} |
73 \end{center} |
27 \end{center} |
74 A proof can be either compound (\isakeyword{proof} -- |
28 A proof can be either compound (\isakeyword{proof} -- |
75 \isakeyword{qed}) or atomic (\isakeyword{by}). A \emph{method} is a |
29 \isakeyword{qed}) or atomic (\isakeyword{by}). A \emph{method} is a |
76 proof method (tactic) offered by the underlying theorem prover. |
30 proof method. |
77 Thus this grammar is generic both w.r.t.\ the logic and the theorem prover. |
|
78 |
31 |
79 This is a typical proof skeleton: |
32 This is a typical proof skeleton: |
80 \begin{center} |
33 \begin{center} |
81 \begin{tabular}{@{}ll} |
34 \begin{tabular}{@{}ll} |
82 \isakeyword{proof}\\ |
35 \isakeyword{proof}\\ |
92 ``---'' is a comment. The intermediate \isakeyword{have}s are only |
45 ``---'' is a comment. The intermediate \isakeyword{have}s are only |
93 there to bridge the gap between the assumption and the conclusion and |
46 there to bridge the gap between the assumption and the conclusion and |
94 do not contribute to the theorem being proved. In contrast, |
47 do not contribute to the theorem being proved. In contrast, |
95 \isakeyword{show} establishes the conclusion of the theorem. |
48 \isakeyword{show} establishes the conclusion of the theorem. |
96 |
49 |
|
50 \subsection{Background} |
|
51 |
|
52 Interactive theorem proving has been dominated by a model of proof |
|
53 that goes back to the LCF system~\cite{LCF}: a proof is a more or less |
|
54 structured sequence of commands that manipulate an implicit proof |
|
55 state. Thus the proof text is only suitable for the machine; for a |
|
56 human, the proof only comes alive when he can see the state changes |
|
57 caused by the stepwise execution of the commands. Such proofs are like |
|
58 uncommented assembly language programs. Their Isabelle incarnation are |
|
59 sequences of \isa{apply}-commands. |
|
60 |
|
61 In contrast there is the model of a mathematics-like proof language |
|
62 pioneered in the Mizar system~\cite{Rudnicki92} and followed by |
|
63 Isar~\cite{WenzelW-JAR}. |
|
64 The most important arguments in favour of this style are |
|
65 \emph{communication} and \emph{maintainance}: structured proofs are |
|
66 immensly more readable and maintainable than \isa{apply}-scripts. |
|
67 |
|
68 For reading this tutorial you should be familiar with natural |
|
69 deduction and the basics of Isabelle/HOL~\cite{LNCS2283} although we |
|
70 summarize the most important aspects of Isabelle below. The |
|
71 definitive Isar reference is its manual~\cite{Isar-Ref-Man}. For an |
|
72 example-based account of Isar's support for reasoning by chains of |
|
73 (in)equations see~\cite{BauerW-TPHOLs01}. |
|
74 |
|
75 |
97 \subsection{Bits of Isabelle} |
76 \subsection{Bits of Isabelle} |
98 |
|
99 We recall some basic notions and notation from Isabelle. For more |
|
100 details and for instructions how to run examples see |
|
101 elsewhere~\cite{LNCS2283}. |
|
102 |
77 |
103 Isabelle's meta-logic comes with a type of \emph{propositions} with |
78 Isabelle's meta-logic comes with a type of \emph{propositions} with |
104 implication $\Longrightarrow$ and a universal quantifier $\bigwedge$ for expressing |
79 implication $\Longrightarrow$ and a universal quantifier $\bigwedge$ for expressing |
105 inference rules and generality. Iterated implications $A_1 \Longrightarrow \dots |
80 inference rules and generality. Iterated implications $A_1 \Longrightarrow \dots |
106 A_n \Longrightarrow A$ may be abbreviated to $[\![ A_1; \dots; A_n ]\!] \Longrightarrow A$. |
81 A_n \Longrightarrow A$ may be abbreviated to $[\![ A_1; \dots; A_n ]\!] \Longrightarrow A$. |
126 step with a given rule, unifying the conclusion of the rule with the |
101 step with a given rule, unifying the conclusion of the rule with the |
127 current subgoal and replacing the subgoal by the premises of the |
102 current subgoal and replacing the subgoal by the premises of the |
128 rule), \isa{simp} (for simplification) and \isa{blast} (for predicate |
103 rule), \isa{simp} (for simplification) and \isa{blast} (for predicate |
129 calculus reasoning). |
104 calculus reasoning). |
130 |
105 |
131 \subsection{Overview of the paper} |
106 \subsection{Advice} |
132 |
107 |
133 The rest of the paper is divided into two parts. |
108 A word of warning for potential writers of Isar proofs. It |
|
109 is easier to write obscure rather than readable texts. Similarly, |
|
110 \isa{apply}-style proofs are sometimes easier to write than readable |
|
111 ones: structure does not emerge automatically but needs to be |
|
112 understood and imposed. If the precise structure of the proof is |
|
113 unclear at beginning, it can be useful to start with \isa{apply} for |
|
114 exploratory purposes until one has found a proof which can be |
|
115 converted into a structured text in a second step. Top down conversion |
|
116 is possible because Isar allows \isa{apply}-style proofs as components |
|
117 of structured ones. |
|
118 |
|
119 Finally, do not be mislead by the simplicity of the formulae being proved, |
|
120 especially in the beginning. Isar has been used very successfully in |
|
121 large applications, for example the formalisation of Java |
|
122 dialects~\cite{KleinN-TOPLAS}. |
|
123 \medskip |
|
124 |
|
125 The rest of this tutorial is divided into two parts. |
134 Section~\ref{sec:Logic} introduces proofs in pure logic based on |
126 Section~\ref{sec:Logic} introduces proofs in pure logic based on |
135 natural deduction. Section~\ref{sec:Induct} is dedicated to induction, |
127 natural deduction. Section~\ref{sec:Induct} is dedicated to induction. |
136 the key reasoning principle for computer science applications. |
|
137 |
|
138 There are two further areas where Isar provides specific support, but |
|
139 which we do not document here. Reasoning by chains of (in)equations is |
|
140 described elsewhere~\cite{BauerW-TPHOLs01}. Reasoning about |
|
141 axiomatically defined structures by means of so called ``locales'' was |
|
142 first described in \cite{KWP-TPHOLs99} but has evolved much since |
|
143 then. |
|
144 |
|
145 Finally, a word of warning for potential writers of Isar proofs. It |
|
146 has always been easier to write obscure rather than readable texts. |
|
147 Similarly, tactic-style proofs are often (though by no means always!) |
|
148 easier to write than readable ones: structure does not emerge |
|
149 automatically but needs to be understood and imposed. If the precise |
|
150 structure of the proof is unclear at beginning, it can be useful to |
|
151 start in a tactic-based style for exploratory purposes until one has |
|
152 found a proof which can be converted into a structured text in a |
|
153 second step. |
|
154 % Top down conversion is possible because Isar |
|
155 %allows tactic-style proofs as components of structured ones. |
|
156 |
|
157 %Do not be mislead by the simplicity of the formulae being proved, |
|
158 %especially in the beginning. Isar has been used very successfully in |
|
159 %large applications, for example the formalisation of Java, in |
|
160 %particular the verification of the bytecode verifier~\cite{KleinN-TCS}. |
|