6 |
6 |
7 chapter \<open>The Isabelle/Isar Framework \label{ch:isar-framework}\<close> |
7 chapter \<open>The Isabelle/Isar Framework \label{ch:isar-framework}\<close> |
8 |
8 |
9 text \<open> |
9 text \<open> |
10 Isabelle/Isar @{cite "Wenzel:1999:TPHOL" and "Wenzel-PhD" and |
10 Isabelle/Isar @{cite "Wenzel:1999:TPHOL" and "Wenzel-PhD" and |
11 "Nipkow-TYPES02" and "Wenzel-Paulson:2006" and "Wenzel:2006:Festschrift"} |
11 "Nipkow-TYPES02" and "Wenzel-Paulson:2006" and "Wenzel:2006:Festschrift"} is |
12 is intended as a generic framework for developing formal |
12 intended as a generic framework for developing formal mathematical documents |
13 mathematical documents with full proof checking. Definitions and |
13 with full proof checking. Definitions and proofs are organized as theories. |
14 proofs are organized as theories. An assembly of theory sources may |
14 An assembly of theory sources may be presented as a printed document; see |
15 be presented as a printed document; see also |
15 also \chref{ch:document-prep}. |
16 \chref{ch:document-prep}. |
16 |
17 |
17 The main objective of Isar is the design of a human-readable structured |
18 The main objective of Isar is the design of a human-readable |
18 proof language, which is called the ``primary proof format'' in Isar |
19 structured proof language, which is called the ``primary proof |
19 terminology. Such a primary proof language is somewhere in the middle |
20 format'' in Isar terminology. Such a primary proof language is |
20 between the extremes of primitive proof objects and actual natural language. |
21 somewhere in the middle between the extremes of primitive proof |
21 In this respect, Isar is a bit more formalistic than Mizar @{cite |
22 objects and actual natural language. In this respect, Isar is a bit |
22 "Trybulec:1993:MizarFeatures" and "Rudnicki:1992:MizarOverview" and |
23 more formalistic than Mizar @{cite "Trybulec:1993:MizarFeatures" and |
23 "Wiedijk:1999:Mizar"}, using logical symbols for certain reasoning schemes |
24 "Rudnicki:1992:MizarOverview" and "Wiedijk:1999:Mizar"}, |
24 where Mizar would prefer English words; see @{cite "Wenzel-Wiedijk:2002"} |
25 using logical symbols for certain reasoning schemes where Mizar |
25 for further comparisons of these systems. |
26 would prefer English words; see @{cite "Wenzel-Wiedijk:2002"} for |
26 |
27 further comparisons of these systems. |
27 So Isar challenges the traditional way of recording informal proofs in |
28 |
28 mathematical prose, as well as the common tendency to see fully formal |
29 So Isar challenges the traditional way of recording informal proofs |
29 proofs directly as objects of some logical calculus (e.g.\ \<open>\<lambda>\<close>-terms in a |
30 in mathematical prose, as well as the common tendency to see fully |
30 version of type theory). In fact, Isar is better understood as an |
31 formal proofs directly as objects of some logical calculus (e.g.\ |
31 interpreter of a simple block-structured language for describing the data |
32 \<open>\<lambda>\<close>-terms in a version of type theory). In fact, Isar is |
32 flow of local facts and goals, interspersed with occasional invocations of |
33 better understood as an interpreter of a simple block-structured |
33 proof methods. Everything is reduced to logical inferences internally, but |
34 language for describing the data flow of local facts and goals, |
34 these steps are somewhat marginal compared to the overall bookkeeping of the |
35 interspersed with occasional invocations of proof methods. |
35 interpretation process. Thanks to careful design of the syntax and semantics |
36 Everything is reduced to logical inferences internally, but these |
36 of Isar language elements, a formal record of Isar instructions may later |
37 steps are somewhat marginal compared to the overall bookkeeping of |
37 appear as an intelligible text to the attentive reader. |
38 the interpretation process. Thanks to careful design of the syntax |
38 |
39 and semantics of Isar language elements, a formal record of Isar |
39 The Isar proof language has emerged from careful analysis of some inherent |
40 instructions may later appear as an intelligible text to the |
40 virtues of the existing logical framework of Isabelle/Pure @{cite |
41 attentive reader. |
41 "paulson-found" and "paulson700"}, notably composition of higher-order |
42 |
42 natural deduction rules, which is a generalization of Gentzen's original |
43 The Isar proof language has emerged from careful analysis of some |
43 calculus @{cite "Gentzen:1935"}. The approach of generic inference systems |
44 inherent virtues of the existing logical framework of Isabelle/Pure |
44 in Pure is continued by Isar towards actual proof texts. |
45 @{cite "paulson-found" and "paulson700"}, notably composition of higher-order |
45 |
46 natural deduction rules, which is a generalization of Gentzen's |
46 Concrete applications require another intermediate layer: an object-logic. |
47 original calculus @{cite "Gentzen:1935"}. The approach of generic |
47 Isabelle/HOL @{cite "isa-tutorial"} (simply-typed set-theory) is being used |
48 inference systems in Pure is continued by Isar towards actual proof |
48 most of the time; Isabelle/ZF @{cite "isabelle-ZF"} is less extensively |
49 texts. |
49 developed, although it would probably fit better for classical mathematics. |
50 |
50 |
51 Concrete applications require another intermediate layer: an |
51 \<^medskip> |
52 object-logic. Isabelle/HOL @{cite "isa-tutorial"} (simply-typed |
52 In order to illustrate natural deduction in Isar, we shall refer to the |
53 set-theory) is being used most of the time; Isabelle/ZF |
53 background theory and library of Isabelle/HOL. This includes common notions |
54 @{cite "isabelle-ZF"} is less extensively developed, although it would |
54 of predicate logic, naive set-theory etc.\ using fairly standard |
55 probably fit better for classical mathematics. |
55 mathematical notation. From the perspective of generic natural deduction |
56 |
56 there is nothing special about the logical connectives of HOL (\<open>\<and>\<close>, \<open>\<or>\<close>, |
57 \<^medskip> |
57 \<open>\<forall>\<close>, \<open>\<exists>\<close>, etc.), only the resulting reasoning principles are relevant to the |
58 In order to illustrate natural deduction in Isar, we shall |
58 user. There are similar rules available for set-theory operators (\<open>\<inter>\<close>, \<open>\<union>\<close>, |
59 refer to the background theory and library of Isabelle/HOL. This |
59 \<open>\<Inter>\<close>, \<open>\<Union>\<close>, etc.), or any other theory developed in the library (lattice |
60 includes common notions of predicate logic, naive set-theory etc.\ |
|
61 using fairly standard mathematical notation. From the perspective |
|
62 of generic natural deduction there is nothing special about the |
|
63 logical connectives of HOL (\<open>\<and>\<close>, \<open>\<or>\<close>, \<open>\<forall>\<close>, |
|
64 \<open>\<exists>\<close>, etc.), only the resulting reasoning principles are |
|
65 relevant to the user. There are similar rules available for |
|
66 set-theory operators (\<open>\<inter>\<close>, \<open>\<union>\<close>, \<open>\<Inter>\<close>, \<open>\<Union>\<close>, etc.), or any other theory developed in the library (lattice |
|
67 theory, topology etc.). |
60 theory, topology etc.). |
68 |
61 |
69 Subsequently we briefly review fragments of Isar proof texts |
62 Subsequently we briefly review fragments of Isar proof texts corresponding |
70 corresponding directly to such general deduction schemes. The |
63 directly to such general deduction schemes. The examples shall refer to |
71 examples shall refer to set-theory, to minimize the danger of |
64 set-theory, to minimize the danger of understanding connectives of predicate |
72 understanding connectives of predicate logic as something special. |
65 logic as something special. |
73 |
66 |
74 \<^medskip> |
67 \<^medskip> |
75 The following deduction performs \<open>\<inter>\<close>-introduction, |
68 The following deduction performs \<open>\<inter>\<close>-introduction, working forwards from |
76 working forwards from assumptions towards the conclusion. We give |
69 assumptions towards the conclusion. We give both the Isar text, and depict |
77 both the Isar text, and depict the primitive rule involved, as |
70 the primitive rule involved, as determined by unification of the problem |
78 determined by unification of the problem against rules that are |
71 against rules that are declared in the library context. |
79 declared in the library context. |
|
80 \<close> |
72 \<close> |
81 |
73 |
82 text_raw \<open>\medskip\begin{minipage}{0.6\textwidth}\<close> |
74 text_raw \<open>\medskip\begin{minipage}{0.6\textwidth}\<close> |
83 |
75 |
84 (*<*) |
76 (*<*) |
155 |
146 |
156 text_raw \<open>\end{minipage}\<close> |
147 text_raw \<open>\end{minipage}\<close> |
157 |
148 |
158 text \<open> |
149 text \<open> |
159 \<^medskip> |
150 \<^medskip> |
160 This Isar reasoning pattern again refers to the |
151 This Isar reasoning pattern again refers to the primitive rule depicted |
161 primitive rule depicted above. The system determines it in the |
152 above. The system determines it in the ``@{command proof}'' step, which |
162 ``@{command proof}'' step, which could have been spelled out more |
153 could have been spelled out more explicitly as ``@{command proof}~\<open>(rule |
163 explicitly as ``@{command proof}~\<open>(rule InterI)\<close>''. Note |
154 InterI)\<close>''. Note that the rule involves both a local parameter @{term "A"} |
164 that the rule involves both a local parameter @{term "A"} and an |
155 and an assumption @{prop "A \<in> \<A>"} in the nested reasoning. This kind of |
165 assumption @{prop "A \<in> \<A>"} in the nested reasoning. This kind of |
|
166 compound rule typically demands a genuine sub-proof in Isar, working |
156 compound rule typically demands a genuine sub-proof in Isar, working |
167 backwards rather than forwards as seen before. In the proof body we |
157 backwards rather than forwards as seen before. In the proof body we |
168 encounter the @{command fix}-@{command assume}-@{command show} |
158 encounter the @{command fix}-@{command assume}-@{command show} outline of |
169 outline of nested sub-proofs that is typical for Isar. The final |
159 nested sub-proofs that is typical for Isar. The final @{command show} is |
170 @{command show} is like @{command have} followed by an additional |
160 like @{command have} followed by an additional refinement of the enclosing |
171 refinement of the enclosing claim, using the rule derived from the |
161 claim, using the rule derived from the proof body. |
172 proof body. |
162 |
173 |
163 \<^medskip> |
174 \<^medskip> |
164 The next example involves @{term "\<Union>\<A>"}, which can be characterized as the |
175 The next example involves @{term "\<Union>\<A>"}, which can be |
165 set of all @{term "x"} such that @{prop "\<exists>A. x \<in> A \<and> A \<in> \<A>"}. The |
176 characterized as the set of all @{term "x"} such that @{prop "\<exists>A. x |
166 elimination rule for @{prop "x \<in> \<Union>\<A>"} does not mention \<open>\<exists>\<close> and \<open>\<and>\<close> at all, |
177 \<in> A \<and> A \<in> \<A>"}. The elimination rule for @{prop "x \<in> \<Union>\<A>"} does |
167 but admits to obtain directly a local @{term "A"} such that @{prop "x \<in> A"} |
178 not mention \<open>\<exists>\<close> and \<open>\<and>\<close> at all, but admits to obtain |
168 and @{prop "A \<in> \<A>"} hold. This corresponds to the following Isar proof and |
179 directly a local @{term "A"} such that @{prop "x \<in> A"} and @{prop "A |
|
180 \<in> \<A>"} hold. This corresponds to the following Isar proof and |
|
181 inference rule, respectively: |
169 inference rule, respectively: |
182 \<close> |
170 \<close> |
183 |
171 |
184 text_raw \<open>\medskip\begin{minipage}{0.6\textwidth}\<close> |
172 text_raw \<open>\medskip\begin{minipage}{0.6\textwidth}\<close> |
185 |
173 |
227 (*<*) |
214 (*<*) |
228 end |
215 end |
229 (*>*) |
216 (*>*) |
230 |
217 |
231 text \<open> |
218 text \<open> |
232 Here we avoid to mention the final conclusion @{prop "C"} |
219 Here we avoid to mention the final conclusion @{prop "C"} and return to |
233 and return to plain forward reasoning. The rule involved in the |
220 plain forward reasoning. The rule involved in the ``@{command ".."}'' proof |
234 ``@{command ".."}'' proof is the same as before. |
221 is the same as before. |
235 \<close> |
222 \<close> |
236 |
223 |
237 |
224 |
238 section \<open>The Pure framework \label{sec:framework-pure}\<close> |
225 section \<open>The Pure framework \label{sec:framework-pure}\<close> |
239 |
226 |
240 text \<open> |
227 text \<open> |
241 The Pure logic @{cite "paulson-found" and "paulson700"} is an intuitionistic |
228 The Pure logic @{cite "paulson-found" and "paulson700"} is an intuitionistic |
242 fragment of higher-order logic @{cite "church40"}. In type-theoretic |
229 fragment of higher-order logic @{cite "church40"}. In type-theoretic |
243 parlance, there are three levels of \<open>\<lambda>\<close>-calculus with |
230 parlance, there are three levels of \<open>\<lambda>\<close>-calculus with corresponding arrows |
244 corresponding arrows \<open>\<Rightarrow>\<close>/\<open>\<And>\<close>/\<open>\<Longrightarrow>\<close>: |
231 \<open>\<Rightarrow>\<close>/\<open>\<And>\<close>/\<open>\<Longrightarrow>\<close>: |
245 |
232 |
246 \<^medskip> |
233 \<^medskip> |
247 \begin{tabular}{ll} |
234 \begin{tabular}{ll} |
248 \<open>\<alpha> \<Rightarrow> \<beta>\<close> & syntactic function space (terms depending on terms) \\ |
235 \<open>\<alpha> \<Rightarrow> \<beta>\<close> & syntactic function space (terms depending on terms) \\ |
249 \<open>\<And>x. B(x)\<close> & universal quantification (proofs depending on terms) \\ |
236 \<open>\<And>x. B(x)\<close> & universal quantification (proofs depending on terms) \\ |
250 \<open>A \<Longrightarrow> B\<close> & implication (proofs depending on proofs) \\ |
237 \<open>A \<Longrightarrow> B\<close> & implication (proofs depending on proofs) \\ |
251 \end{tabular} |
238 \end{tabular} |
252 \<^medskip> |
239 \<^medskip> |
253 |
240 |
254 Here only the types of syntactic terms, and the |
241 Here only the types of syntactic terms, and the propositions of proof terms |
255 propositions of proof terms have been shown. The \<open>\<lambda>\<close>-structure of proofs can be recorded as an optional feature of |
242 have been shown. The \<open>\<lambda>\<close>-structure of proofs can be recorded as an optional |
256 the Pure inference kernel @{cite "Berghofer-Nipkow:2000:TPHOL"}, but |
243 feature of the Pure inference kernel @{cite "Berghofer-Nipkow:2000:TPHOL"}, |
257 the formal system can never depend on them due to \<^emph>\<open>proof |
244 but the formal system can never depend on them due to \<^emph>\<open>proof irrelevance\<close>. |
258 irrelevance\<close>. |
245 |
259 |
246 On top of this most primitive layer of proofs, Pure implements a generic |
260 On top of this most primitive layer of proofs, Pure implements a |
247 calculus for nested natural deduction rules, similar to @{cite |
261 generic calculus for nested natural deduction rules, similar to |
248 "Schroeder-Heister:1984"}. Here object-logic inferences are internalized as |
262 @{cite "Schroeder-Heister:1984"}. Here object-logic inferences are |
249 formulae over \<open>\<And>\<close> and \<open>\<Longrightarrow>\<close>. Combining such rule statements may involve |
263 internalized as formulae over \<open>\<And>\<close> and \<open>\<Longrightarrow>\<close>. |
250 higher-order unification @{cite "paulson-natural"}. |
264 Combining such rule statements may involve higher-order unification |
|
265 @{cite "paulson-natural"}. |
|
266 \<close> |
251 \<close> |
267 |
252 |
268 |
253 |
269 subsection \<open>Primitive inferences\<close> |
254 subsection \<open>Primitive inferences\<close> |
270 |
255 |
271 text \<open> |
256 text \<open> |
272 Term syntax provides explicit notation for abstraction \<open>\<lambda>x :: |
257 Term syntax provides explicit notation for abstraction \<open>\<lambda>x :: \<alpha>. b(x)\<close> and |
273 \<alpha>. b(x)\<close> and application \<open>b a\<close>, while types are usually |
258 application \<open>b a\<close>, while types are usually implicit thanks to |
274 implicit thanks to type-inference; terms of type \<open>prop\<close> are |
259 type-inference; terms of type \<open>prop\<close> are called propositions. Logical |
275 called propositions. Logical statements are composed via \<open>\<And>x |
260 statements are composed via \<open>\<And>x :: \<alpha>. B(x)\<close> and \<open>A \<Longrightarrow> B\<close>. Primitive reasoning |
276 :: \<alpha>. B(x)\<close> and \<open>A \<Longrightarrow> B\<close>. Primitive reasoning operates on |
261 operates on judgments of the form \<open>\<Gamma> \<turnstile> \<phi>\<close>, with standard introduction and |
277 judgments of the form \<open>\<Gamma> \<turnstile> \<phi>\<close>, with standard introduction |
262 elimination rules for \<open>\<And>\<close> and \<open>\<Longrightarrow>\<close> that refer to fixed parameters \<open>x\<^sub>1, \<dots>, |
278 and elimination rules for \<open>\<And>\<close> and \<open>\<Longrightarrow>\<close> that refer to |
263 x\<^sub>m\<close> and hypotheses \<open>A\<^sub>1, \<dots>, A\<^sub>n\<close> from the context \<open>\<Gamma>\<close>; the corresponding |
279 fixed parameters \<open>x\<^sub>1, \<dots>, x\<^sub>m\<close> and hypotheses |
264 proof terms are left implicit. The subsequent inference rules define \<open>\<Gamma> \<turnstile> \<phi>\<close> |
280 \<open>A\<^sub>1, \<dots>, A\<^sub>n\<close> from the context \<open>\<Gamma>\<close>; |
265 inductively, relative to a collection of axioms: |
281 the corresponding proof terms are left implicit. The subsequent |
|
282 inference rules define \<open>\<Gamma> \<turnstile> \<phi>\<close> inductively, relative to a |
|
283 collection of axioms: |
|
284 |
266 |
285 \[ |
267 \[ |
286 \infer{\<open>\<turnstile> A\<close>}{(\<open>A\<close> \mbox{~axiom})} |
268 \infer{\<open>\<turnstile> A\<close>}{(\<open>A\<close> \mbox{~axiom})} |
287 \qquad |
269 \qquad |
288 \infer{\<open>A \<turnstile> A\<close>}{} |
270 \infer{\<open>A \<turnstile> A\<close>}{} |
298 \infer{\<open>\<Gamma> - A \<turnstile> A \<Longrightarrow> B\<close>}{\<open>\<Gamma> \<turnstile> B\<close>} |
280 \infer{\<open>\<Gamma> - A \<turnstile> A \<Longrightarrow> B\<close>}{\<open>\<Gamma> \<turnstile> B\<close>} |
299 \qquad |
281 \qquad |
300 \infer{\<open>\<Gamma>\<^sub>1 \<union> \<Gamma>\<^sub>2 \<turnstile> B\<close>}{\<open>\<Gamma>\<^sub>1 \<turnstile> A \<Longrightarrow> B\<close> & \<open>\<Gamma>\<^sub>2 \<turnstile> A\<close>} |
282 \infer{\<open>\<Gamma>\<^sub>1 \<union> \<Gamma>\<^sub>2 \<turnstile> B\<close>}{\<open>\<Gamma>\<^sub>1 \<turnstile> A \<Longrightarrow> B\<close> & \<open>\<Gamma>\<^sub>2 \<turnstile> A\<close>} |
301 \] |
283 \] |
302 |
284 |
303 Furthermore, Pure provides a built-in equality \<open>\<equiv> :: \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> |
285 Furthermore, Pure provides a built-in equality \<open>\<equiv> :: \<alpha> \<Rightarrow> \<alpha> \<Rightarrow> prop\<close> with |
304 prop\<close> with axioms for reflexivity, substitution, extensionality, |
286 axioms for reflexivity, substitution, extensionality, and \<open>\<alpha>\<beta>\<eta>\<close>-conversion |
305 and \<open>\<alpha>\<beta>\<eta>\<close>-conversion on \<open>\<lambda>\<close>-terms. |
287 on \<open>\<lambda>\<close>-terms. |
306 |
288 |
307 \<^medskip> |
289 \<^medskip> |
308 An object-logic introduces another layer on top of Pure, |
290 An object-logic introduces another layer on top of Pure, e.g.\ with types |
309 e.g.\ with types \<open>i\<close> for individuals and \<open>o\<close> for |
291 \<open>i\<close> for individuals and \<open>o\<close> for propositions, term constants \<open>Trueprop :: o |
310 propositions, term constants \<open>Trueprop :: o \<Rightarrow> prop\<close> as |
292 \<Rightarrow> prop\<close> as (implicit) derivability judgment and connectives like \<open>\<and> :: o \<Rightarrow> o |
311 (implicit) derivability judgment and connectives like \<open>\<and> :: o |
293 \<Rightarrow> o\<close> or \<open>\<forall> :: (i \<Rightarrow> o) \<Rightarrow> o\<close>, and axioms for object-level rules such as |
312 \<Rightarrow> o \<Rightarrow> o\<close> or \<open>\<forall> :: (i \<Rightarrow> o) \<Rightarrow> o\<close>, and axioms for object-level |
294 \<open>conjI: A \<Longrightarrow> B \<Longrightarrow> A \<and> B\<close> or \<open>allI: (\<And>x. B x) \<Longrightarrow> \<forall>x. B x\<close>. Derived object rules |
313 rules such as \<open>conjI: A \<Longrightarrow> B \<Longrightarrow> A \<and> B\<close> or \<open>allI: (\<And>x. B |
295 are represented as theorems of Pure. After the initial object-logic setup, |
314 x) \<Longrightarrow> \<forall>x. B x\<close>. Derived object rules are represented as theorems of |
296 further axiomatizations are usually avoided; plain definitions and derived |
315 Pure. After the initial object-logic setup, further axiomatizations |
297 principles are used exclusively. |
316 are usually avoided; plain definitions and derived principles are |
|
317 used exclusively. |
|
318 \<close> |
298 \<close> |
319 |
299 |
320 |
300 |
321 subsection \<open>Reasoning with rules \label{sec:framework-resolution}\<close> |
301 subsection \<open>Reasoning with rules \label{sec:framework-resolution}\<close> |
322 |
302 |
323 text \<open> |
303 text \<open> |
324 Primitive inferences mostly serve foundational purposes. The main |
304 Primitive inferences mostly serve foundational purposes. The main reasoning |
325 reasoning mechanisms of Pure operate on nested natural deduction |
305 mechanisms of Pure operate on nested natural deduction rules expressed as |
326 rules expressed as formulae, using \<open>\<And>\<close> to bind local |
306 formulae, using \<open>\<And>\<close> to bind local parameters and \<open>\<Longrightarrow>\<close> to express entailment. |
327 parameters and \<open>\<Longrightarrow>\<close> to express entailment. Multiple |
307 Multiple parameters and premises are represented by repeating these |
328 parameters and premises are represented by repeating these |
|
329 connectives in a right-associative manner. |
308 connectives in a right-associative manner. |
330 |
309 |
331 Since \<open>\<And>\<close> and \<open>\<Longrightarrow>\<close> commute thanks to the theorem |
310 Since \<open>\<And>\<close> and \<open>\<Longrightarrow>\<close> commute thanks to the theorem @{prop "(A \<Longrightarrow> (\<And>x. B x)) \<equiv> |
332 @{prop "(A \<Longrightarrow> (\<And>x. B x)) \<equiv> (\<And>x. A \<Longrightarrow> B x)"}, we may assume w.l.o.g.\ |
311 (\<And>x. A \<Longrightarrow> B x)"}, we may assume w.l.o.g.\ that rule statements always observe |
333 that rule statements always observe the normal form where |
312 the normal form where quantifiers are pulled in front of implications at |
334 quantifiers are pulled in front of implications at each level of |
313 each level of nesting. This means that any Pure proposition may be presented |
335 nesting. This means that any Pure proposition may be presented as a |
314 as a \<^emph>\<open>Hereditary Harrop Formula\<close> @{cite "Miller:1991"} which is of the form |
336 \<^emph>\<open>Hereditary Harrop Formula\<close> @{cite "Miller:1991"} which is of the |
315 \<open>\<And>x\<^sub>1 \<dots> x\<^sub>m. H\<^sub>1 \<Longrightarrow> \<dots> H\<^sub>n \<Longrightarrow> A\<close> for \<open>m, n \<ge> 0\<close>, and \<open>A\<close> atomic, and \<open>H\<^sub>1, \<dots>, |
337 form \<open>\<And>x\<^sub>1 \<dots> x\<^sub>m. H\<^sub>1 \<Longrightarrow> \<dots> H\<^sub>n \<Longrightarrow> |
316 H\<^sub>n\<close> being recursively of the same format. Following the convention that |
338 A\<close> for \<open>m, n \<ge> 0\<close>, and \<open>A\<close> atomic, and \<open>H\<^sub>1, \<dots>, H\<^sub>n\<close> being recursively of the same format. |
317 outermost quantifiers are implicit, Horn clauses \<open>A\<^sub>1 \<Longrightarrow> \<dots> A\<^sub>n \<Longrightarrow> A\<close> are a |
339 Following the convention that outermost quantifiers are implicit, |
318 special case of this. |
340 Horn clauses \<open>A\<^sub>1 \<Longrightarrow> \<dots> A\<^sub>n \<Longrightarrow> A\<close> are a special |
319 |
341 case of this. |
320 For example, \<open>\<inter>\<close>-introduction rule encountered before is represented as a |
342 |
321 Pure theorem as follows: |
343 For example, \<open>\<inter>\<close>-introduction rule encountered before is |
|
344 represented as a Pure theorem as follows: |
|
345 \[ |
322 \[ |
346 \<open>IntI:\<close>~@{prop "x \<in> A \<Longrightarrow> x \<in> B \<Longrightarrow> x \<in> A \<inter> B"} |
323 \<open>IntI:\<close>~@{prop "x \<in> A \<Longrightarrow> x \<in> B \<Longrightarrow> x \<in> A \<inter> B"} |
347 \] |
324 \] |
348 |
325 |
349 This is a plain Horn clause, since no further nesting on |
326 This is a plain Horn clause, since no further nesting on the left is |
350 the left is involved. The general \<open>\<Inter>\<close>-introduction |
327 involved. The general \<open>\<Inter>\<close>-introduction corresponds to a Hereditary Harrop |
351 corresponds to a Hereditary Harrop Formula with one additional level |
328 Formula with one additional level of nesting: |
352 of nesting: |
|
353 \[ |
329 \[ |
354 \<open>InterI:\<close>~@{prop "(\<And>A. A \<in> \<A> \<Longrightarrow> x \<in> A) \<Longrightarrow> x \<in> \<Inter>\<A>"} |
330 \<open>InterI:\<close>~@{prop "(\<And>A. A \<in> \<A> \<Longrightarrow> x \<in> A) \<Longrightarrow> x \<in> \<Inter>\<A>"} |
355 \] |
331 \] |
356 |
332 |
357 \<^medskip> |
333 \<^medskip> |
358 Goals are also represented as rules: \<open>A\<^sub>1 \<Longrightarrow> |
334 Goals are also represented as rules: \<open>A\<^sub>1 \<Longrightarrow> \<dots> A\<^sub>n \<Longrightarrow> C\<close> states that the |
359 \<dots> A\<^sub>n \<Longrightarrow> C\<close> states that the sub-goals \<open>A\<^sub>1, \<dots>, |
335 sub-goals \<open>A\<^sub>1, \<dots>, A\<^sub>n\<close> entail the result \<open>C\<close>; for \<open>n = 0\<close> the goal is |
360 A\<^sub>n\<close> entail the result \<open>C\<close>; for \<open>n = 0\<close> the |
336 finished. To allow \<open>C\<close> being a rule statement itself, we introduce the |
361 goal is finished. To allow \<open>C\<close> being a rule statement |
337 protective marker \<open># :: prop \<Rightarrow> prop\<close>, which is defined as identity and |
362 itself, we introduce the protective marker \<open># :: prop \<Rightarrow> |
338 hidden from the user. We initialize and finish goal states as follows: |
363 prop\<close>, which is defined as identity and hidden from the user. We |
|
364 initialize and finish goal states as follows: |
|
365 |
339 |
366 \[ |
340 \[ |
367 \begin{array}{c@ {\qquad}c} |
341 \begin{array}{c@ {\qquad}c} |
368 \infer[(@{inference_def init})]{\<open>C \<Longrightarrow> #C\<close>}{} & |
342 \infer[(@{inference_def init})]{\<open>C \<Longrightarrow> #C\<close>}{} & |
369 \infer[(@{inference_def finish})]{\<open>C\<close>}{\<open>#C\<close>} |
343 \infer[(@{inference_def finish})]{\<open>C\<close>}{\<open>#C\<close>} |
370 \end{array} |
344 \end{array} |
371 \] |
345 \] |
372 |
346 |
373 Goal states are refined in intermediate proof steps until |
347 Goal states are refined in intermediate proof steps until a finished form is |
374 a finished form is achieved. Here the two main reasoning principles |
348 achieved. Here the two main reasoning principles are @{inference |
375 are @{inference resolution}, for back-chaining a rule against a |
349 resolution}, for back-chaining a rule against a sub-goal (replacing it by |
376 sub-goal (replacing it by zero or more sub-goals), and @{inference |
350 zero or more sub-goals), and @{inference assumption}, for solving a sub-goal |
377 assumption}, for solving a sub-goal (finding a short-circuit with |
351 (finding a short-circuit with local assumptions). Below \<open>\<^vec>x\<close> stands |
378 local assumptions). Below \<open>\<^vec>x\<close> stands for \<open>x\<^sub>1, \<dots>, x\<^sub>n\<close> (\<open>n \<ge> 0\<close>). |
352 for \<open>x\<^sub>1, \<dots>, x\<^sub>n\<close> (\<open>n \<ge> 0\<close>). |
379 |
353 |
380 \[ |
354 \[ |
381 \infer[(@{inference_def resolution})] |
355 \infer[(@{inference_def resolution})] |
382 {\<open>(\<And>\<^vec>x. \<^vec>H \<^vec>x \<Longrightarrow> \<^vec>A (\<^vec>a \<^vec>x))\<vartheta> \<Longrightarrow> C\<vartheta>\<close>} |
356 {\<open>(\<And>\<^vec>x. \<^vec>H \<^vec>x \<Longrightarrow> \<^vec>A (\<^vec>a \<^vec>x))\<vartheta> \<Longrightarrow> C\<vartheta>\<close>} |
383 {\begin{tabular}{rl} |
357 {\begin{tabular}{rl} |
440 \<open>(\<lambda>\<^vec>x. G\<^sub>j (\<^vec>a \<^vec>x))\<vartheta> = #H\<^sub>i\<vartheta>\<close> \\ |
413 \<open>(\<lambda>\<^vec>x. G\<^sub>j (\<^vec>a \<^vec>x))\<vartheta> = #H\<^sub>i\<vartheta>\<close> \\ |
441 & \quad (for each marked \<open>G\<^sub>j\<close> some \<open>#H\<^sub>i\<close>) \\ |
414 & \quad (for each marked \<open>G\<^sub>j\<close> some \<open>#H\<^sub>i\<close>) \\ |
442 \end{tabular}} |
415 \end{tabular}} |
443 \] |
416 \] |
444 |
417 |
445 Here the \<open>sub\<hyphen>proof\<close> rule stems from the |
418 Here the \<open>sub\<hyphen>proof\<close> rule stems from the main @{command fix}-@{command |
446 main @{command fix}-@{command assume}-@{command show} outline of |
419 assume}-@{command show} outline of Isar (cf.\ |
447 Isar (cf.\ \secref{sec:framework-subproof}): each assumption |
420 \secref{sec:framework-subproof}): each assumption indicated in the text |
448 indicated in the text results in a marked premise \<open>G\<close> above. |
421 results in a marked premise \<open>G\<close> above. The marking enforces resolution |
449 The marking enforces resolution against one of the sub-goal's |
422 against one of the sub-goal's premises. Consequently, @{command |
450 premises. Consequently, @{command fix}-@{command assume}-@{command |
423 fix}-@{command assume}-@{command show} enables to fit the result of a |
451 show} enables to fit the result of a sub-proof quite robustly into a |
424 sub-proof quite robustly into a pending sub-goal, while maintaining a good |
452 pending sub-goal, while maintaining a good measure of flexibility. |
425 measure of flexibility. |
453 \<close> |
426 \<close> |
454 |
427 |
455 |
428 |
456 section \<open>The Isar proof language \label{sec:framework-isar}\<close> |
429 section \<open>The Isar proof language \label{sec:framework-isar}\<close> |
457 |
430 |
458 text \<open> |
431 text \<open> |
459 Structured proofs are presented as high-level expressions for |
432 Structured proofs are presented as high-level expressions for composing |
460 composing entities of Pure (propositions, facts, and goals). The |
433 entities of Pure (propositions, facts, and goals). The Isar proof language |
461 Isar proof language allows to organize reasoning within the |
434 allows to organize reasoning within the underlying rule calculus of Pure, |
462 underlying rule calculus of Pure, but Isar is not another logical |
435 but Isar is not another logical calculus! |
463 calculus! |
436 |
464 |
437 Isar is an exercise in sound minimalism. Approximately half of the language |
465 Isar is an exercise in sound minimalism. Approximately half of the |
438 is introduced as primitive, the rest defined as derived concepts. The |
466 language is introduced as primitive, the rest defined as derived |
439 following grammar describes the core language (category \<open>proof\<close>), which is |
467 concepts. The following grammar describes the core language |
440 embedded into theory specification elements such as @{command theorem}; see |
468 (category \<open>proof\<close>), which is embedded into theory |
441 also \secref{sec:framework-stmt} for the separate category \<open>statement\<close>. |
469 specification elements such as @{command theorem}; see also |
|
470 \secref{sec:framework-stmt} for the separate category \<open>statement\<close>. |
|
471 |
442 |
472 \<^medskip> |
443 \<^medskip> |
473 \begin{tabular}{rcl} |
444 \begin{tabular}{rcl} |
474 \<open>theory\<hyphen>stmt\<close> & = & @{command "theorem"}~\<open>statement proof |\<close>~~@{command "definition"}~\<open>\<dots> | \<dots>\<close> \\[1ex] |
445 \<open>theory\<hyphen>stmt\<close> & = & @{command "theorem"}~\<open>statement proof |\<close>~~@{command "definition"}~\<open>\<dots> | \<dots>\<close> \\[1ex] |
475 |
446 |
488 \<open>goal\<close> & = & @{command "have"}~\<open>name: props proof\<close> \\ |
459 \<open>goal\<close> & = & @{command "have"}~\<open>name: props proof\<close> \\ |
489 & \<open>|\<close> & @{command "show"}~\<open>name: props proof\<close> \\ |
460 & \<open>|\<close> & @{command "show"}~\<open>name: props proof\<close> \\ |
490 \end{tabular} |
461 \end{tabular} |
491 |
462 |
492 \<^medskip> |
463 \<^medskip> |
493 Simultaneous propositions or facts may be separated by the |
464 Simultaneous propositions or facts may be separated by the @{keyword "and"} |
494 @{keyword "and"} keyword. |
465 keyword. |
495 |
466 |
496 \<^medskip> |
467 \<^medskip> |
497 The syntax for terms and propositions is inherited from |
468 The syntax for terms and propositions is inherited from Pure (and the |
498 Pure (and the object-logic). A \<open>pattern\<close> is a \<open>term\<close> with schematic variables, to be bound by higher-order |
469 object-logic). A \<open>pattern\<close> is a \<open>term\<close> with schematic variables, to be bound |
499 matching. |
470 by higher-order matching. |
500 |
471 |
501 \<^medskip> |
472 \<^medskip> |
502 Facts may be referenced by name or proposition. For |
473 Facts may be referenced by name or proposition. For example, the result of |
503 example, the result of ``@{command have}~\<open>a: A \<langle>proof\<rangle>\<close>'' |
474 ``@{command have}~\<open>a: A \<langle>proof\<rangle>\<close>'' becomes available both as \<open>a\<close> and |
504 becomes available both as \<open>a\<close> and |
475 \isacharbackquoteopen\<open>A\<close>\isacharbackquoteclose. Moreover, fact expressions |
505 \isacharbackquoteopen\<open>A\<close>\isacharbackquoteclose. Moreover, |
476 may involve attributes that modify either the theorem or the background |
506 fact expressions may involve attributes that modify either the |
477 context. For example, the expression ``\<open>a [OF b]\<close>'' refers to the |
507 theorem or the background context. For example, the expression |
478 composition of two facts according to the @{inference resolution} inference |
508 ``\<open>a [OF b]\<close>'' refers to the composition of two facts |
479 of \secref{sec:framework-resolution}, while ``\<open>a [intro]\<close>'' declares a fact |
509 according to the @{inference resolution} inference of |
480 as introduction rule in the context. |
510 \secref{sec:framework-resolution}, while ``\<open>a [intro]\<close>'' |
481 |
511 declares a fact as introduction rule in the context. |
482 The special fact called ``@{fact this}'' always refers to the last result, |
512 |
483 as produced by @{command note}, @{command assume}, @{command have}, or |
513 The special fact called ``@{fact this}'' always refers to the last |
484 @{command show}. Since @{command note} occurs frequently together with |
514 result, as produced by @{command note}, @{command assume}, @{command |
485 @{command then} we provide some abbreviations: |
515 have}, or @{command show}. Since @{command note} occurs |
|
516 frequently together with @{command then} we provide some |
|
517 abbreviations: |
|
518 |
486 |
519 \<^medskip> |
487 \<^medskip> |
520 \begin{tabular}{rcl} |
488 \begin{tabular}{rcl} |
521 @{command from}~\<open>a\<close> & \<open>\<equiv>\<close> & @{command note}~\<open>a\<close>~@{command then} \\ |
489 @{command from}~\<open>a\<close> & \<open>\<equiv>\<close> & @{command note}~\<open>a\<close>~@{command then} \\ |
522 @{command with}~\<open>a\<close> & \<open>\<equiv>\<close> & @{command from}~\<open>a \<AND> this\<close> \\ |
490 @{command with}~\<open>a\<close> & \<open>\<equiv>\<close> & @{command from}~\<open>a \<AND> this\<close> \\ |
523 \end{tabular} |
491 \end{tabular} |
524 \<^medskip> |
492 \<^medskip> |
525 |
493 |
526 The \<open>method\<close> category is essentially a parameter and may be |
494 The \<open>method\<close> category is essentially a parameter and may be populated later. |
527 populated later. Methods use the facts indicated by @{command |
495 Methods use the facts indicated by @{command "then"} or @{command using}, |
528 "then"} or @{command using}, and then operate on the goal state. |
496 and then operate on the goal state. Some basic methods are predefined: |
529 Some basic methods are predefined: ``@{method "-"}'' leaves the goal |
497 ``@{method "-"}'' leaves the goal unchanged, ``@{method this}'' applies the |
530 unchanged, ``@{method this}'' applies the facts as rules to the |
498 facts as rules to the goal, ``@{method (Pure) "rule"}'' applies the facts to |
531 goal, ``@{method (Pure) "rule"}'' applies the facts to another rule and the |
499 another rule and the result to the goal (both ``@{method this}'' and |
532 result to the goal (both ``@{method this}'' and ``@{method (Pure) rule}'' |
500 ``@{method (Pure) rule}'' refer to @{inference resolution} of |
533 refer to @{inference resolution} of |
501 \secref{sec:framework-resolution}). The secondary arguments to ``@{method |
534 \secref{sec:framework-resolution}). The secondary arguments to |
502 (Pure) rule}'' may be specified explicitly as in ``\<open>(rule a)\<close>'', or picked |
535 ``@{method (Pure) rule}'' may be specified explicitly as in ``\<open>(rule |
503 from the context. In the latter case, the system first tries rules declared |
536 a)\<close>'', or picked from the context. In the latter case, the system |
504 as @{attribute (Pure) elim} or @{attribute (Pure) dest}, followed by those |
537 first tries rules declared as @{attribute (Pure) elim} or |
505 declared as @{attribute (Pure) intro}. |
538 @{attribute (Pure) dest}, followed by those declared as @{attribute |
506 |
539 (Pure) intro}. |
507 The default method for @{command proof} is ``@{method standard}'' (arguments |
540 |
508 picked from the context), for @{command qed} it is ``@{method "succeed"}''. |
541 The default method for @{command proof} is ``@{method standard}'' |
509 Further abbreviations for terminal proof steps are ``@{command |
542 (arguments picked from the context), for @{command qed} it is |
510 "by"}~\<open>method\<^sub>1 method\<^sub>2\<close>'' for ``@{command proof}~\<open>method\<^sub>1\<close>~@{command |
543 ``@{method "succeed"}''. Further abbreviations for terminal proof steps |
511 qed}~\<open>method\<^sub>2\<close>'', and ``@{command ".."}'' for ``@{command "by"}~@{method |
544 are ``@{command "by"}~\<open>method\<^sub>1 method\<^sub>2\<close>'' for |
512 standard}, and ``@{command "."}'' for ``@{command "by"}~@{method this}''. |
545 ``@{command proof}~\<open>method\<^sub>1\<close>~@{command qed}~\<open>method\<^sub>2\<close>'', and ``@{command ".."}'' for ``@{command |
513 The @{command unfolding} element operates directly on the current facts and |
546 "by"}~@{method standard}, and ``@{command "."}'' for ``@{command |
514 goal by applying equalities. |
547 "by"}~@{method this}''. The @{command unfolding} element operates |
|
548 directly on the current facts and goal by applying equalities. |
|
549 |
515 |
550 \<^medskip> |
516 \<^medskip> |
551 Block structure can be indicated explicitly by ``@{command |
517 Block structure can be indicated explicitly by ``@{command |
552 "{"}~\<open>\<dots>\<close>~@{command "}"}'', although the body of a sub-proof |
518 "{"}~\<open>\<dots>\<close>~@{command "}"}'', although the body of a sub-proof already involves |
553 already involves implicit nesting. In any case, @{command next} |
519 implicit nesting. In any case, @{command next} jumps into the next section |
554 jumps into the next section of a block, i.e.\ it acts like closing |
520 of a block, i.e.\ it acts like closing an implicit block scope and opening |
555 an implicit block scope and opening another one; there is no direct |
521 another one; there is no direct correspondence to subgoals here. |
556 correspondence to subgoals here. |
522 |
557 |
523 The remaining elements @{command fix} and @{command assume} build up a local |
558 The remaining elements @{command fix} and @{command assume} build up |
524 context (see \secref{sec:framework-context}), while @{command show} refines |
559 a local context (see \secref{sec:framework-context}), while |
525 a pending sub-goal by the rule resulting from a nested sub-proof (see |
560 @{command show} refines a pending sub-goal by the rule resulting |
526 \secref{sec:framework-subproof}). Further derived concepts will support |
561 from a nested sub-proof (see \secref{sec:framework-subproof}). |
527 calculational reasoning (see \secref{sec:framework-calc}). |
562 Further derived concepts will support calculational reasoning (see |
|
563 \secref{sec:framework-calc}). |
|
564 \<close> |
528 \<close> |
565 |
529 |
566 |
530 |
567 subsection \<open>Context elements \label{sec:framework-context}\<close> |
531 subsection \<open>Context elements \label{sec:framework-context}\<close> |
568 |
532 |
569 text \<open> |
533 text \<open> |
570 In judgments \<open>\<Gamma> \<turnstile> \<phi>\<close> of the primitive framework, \<open>\<Gamma>\<close> |
534 In judgments \<open>\<Gamma> \<turnstile> \<phi>\<close> of the primitive framework, \<open>\<Gamma>\<close> essentially acts like a |
571 essentially acts like a proof context. Isar elaborates this idea |
535 proof context. Isar elaborates this idea towards a higher-level notion, with |
572 towards a higher-level notion, with additional information for |
536 additional information for type-inference, term abbreviations, local facts, |
573 type-inference, term abbreviations, local facts, hypotheses etc. |
537 hypotheses etc. |
574 |
538 |
575 The element @{command fix}~\<open>x :: \<alpha>\<close> declares a local |
539 The element @{command fix}~\<open>x :: \<alpha>\<close> declares a local parameter, i.e.\ an |
576 parameter, i.e.\ an arbitrary-but-fixed entity of a given type; in |
540 arbitrary-but-fixed entity of a given type; in results exported from the |
577 results exported from the context, \<open>x\<close> may become anything. |
541 context, \<open>x\<close> may become anything. The @{command assume}~\<open>\<guillemotleft>inference\<guillemotright>\<close> |
578 The @{command assume}~\<open>\<guillemotleft>inference\<guillemotright>\<close> element provides a |
542 element provides a general interface to hypotheses: ``@{command |
579 general interface to hypotheses: ``@{command assume}~\<open>\<guillemotleft>inference\<guillemotright> A\<close>'' produces \<open>A \<turnstile> A\<close> locally, while the |
543 assume}~\<open>\<guillemotleft>inference\<guillemotright> A\<close>'' produces \<open>A \<turnstile> A\<close> locally, while the included |
580 included inference tells how to discharge \<open>A\<close> from results |
544 inference tells how to discharge \<open>A\<close> from results \<open>A \<turnstile> B\<close> later on. There is |
581 \<open>A \<turnstile> B\<close> later on. There is no user-syntax for \<open>\<guillemotleft>inference\<guillemotright>\<close>, i.e.\ it may only occur internally when derived |
545 no user-syntax for \<open>\<guillemotleft>inference\<guillemotright>\<close>, i.e.\ it may only occur internally when |
582 commands are defined in ML. |
546 derived commands are defined in ML. |
583 |
547 |
584 At the user-level, the default inference for @{command assume} is |
548 At the user-level, the default inference for @{command assume} is |
585 @{inference discharge} as given below. The additional variants |
549 @{inference discharge} as given below. The additional variants @{command |
586 @{command presume} and @{command def} are defined as follows: |
550 presume} and @{command def} are defined as follows: |
587 |
551 |
588 \<^medskip> |
552 \<^medskip> |
589 \begin{tabular}{rcl} |
553 \begin{tabular}{rcl} |
590 @{command presume}~\<open>A\<close> & \<open>\<equiv>\<close> & @{command assume}~\<open>\<guillemotleft>weak\<hyphen>discharge\<guillemotright> A\<close> \\ |
554 @{command presume}~\<open>A\<close> & \<open>\<equiv>\<close> & @{command assume}~\<open>\<guillemotleft>weak\<hyphen>discharge\<guillemotright> A\<close> \\ |
591 @{command def}~\<open>x \<equiv> a\<close> & \<open>\<equiv>\<close> & @{command fix}~\<open>x\<close>~@{command assume}~\<open>\<guillemotleft>expansion\<guillemotright> x \<equiv> a\<close> \\ |
555 @{command def}~\<open>x \<equiv> a\<close> & \<open>\<equiv>\<close> & @{command fix}~\<open>x\<close>~@{command assume}~\<open>\<guillemotleft>expansion\<guillemotright> x \<equiv> a\<close> \\ |
769 |
728 |
770 text_raw \<open>\end{minipage}\<close> |
729 text_raw \<open>\end{minipage}\<close> |
771 |
730 |
772 text \<open> |
731 text \<open> |
773 \<^medskip> |
732 \<^medskip> |
774 Here local facts \isacharbackquoteopen\<open>A |
733 Here local facts \isacharbackquoteopen\<open>A x\<close>\isacharbackquoteclose\ and |
775 x\<close>\isacharbackquoteclose\ and \isacharbackquoteopen\<open>B |
734 \isacharbackquoteopen\<open>B y\<close>\isacharbackquoteclose\ are referenced |
776 y\<close>\isacharbackquoteclose\ are referenced immediately; there is no |
735 immediately; there is no need to decompose the logical rule structure again. |
777 need to decompose the logical rule structure again. In the second |
736 In the second proof the final ``@{command then}~@{command |
778 proof the final ``@{command then}~@{command show}~\<open>thesis\<close>~@{command ".."}'' involves the local rule case \<open>\<And>x |
737 show}~\<open>thesis\<close>~@{command ".."}'' involves the local rule case \<open>\<And>x y. A x \<Longrightarrow> B |
779 y. A x \<Longrightarrow> B y \<Longrightarrow> thesis\<close> for the particular instance of terms \<open>a\<close> and \<open>b\<close> produced in the body. |
738 y \<Longrightarrow> thesis\<close> for the particular instance of terms \<open>a\<close> and \<open>b\<close> produced in the |
780 \<close> |
739 body. \<close> |
781 |
740 |
782 |
741 |
783 subsection \<open>Structured proof refinement \label{sec:framework-subproof}\<close> |
742 subsection \<open>Structured proof refinement \label{sec:framework-subproof}\<close> |
784 |
743 |
785 text \<open> |
744 text \<open> |
786 By breaking up the grammar for the Isar proof language, we may |
745 By breaking up the grammar for the Isar proof language, we may understand a |
787 understand a proof text as a linear sequence of individual proof |
746 proof text as a linear sequence of individual proof commands. These are |
788 commands. These are interpreted as transitions of the Isar virtual |
747 interpreted as transitions of the Isar virtual machine (Isar/VM), which |
789 machine (Isar/VM), which operates on a block-structured |
748 operates on a block-structured configuration in single steps. This allows |
790 configuration in single steps. This allows users to write proof |
749 users to write proof texts in an incremental manner, and inspect |
791 texts in an incremental manner, and inspect intermediate |
750 intermediate configurations for debugging. |
792 configurations for debugging. |
751 |
793 |
752 The basic idea is analogous to evaluating algebraic expressions on a stack |
794 The basic idea is analogous to evaluating algebraic expressions on a |
753 machine: \<open>(a + b) \<cdot> c\<close> then corresponds to a sequence of single transitions |
795 stack machine: \<open>(a + b) \<cdot> c\<close> then corresponds to a sequence |
754 for each symbol \<open>(, a, +, b, ), \<cdot>, c\<close>. In Isar the algebraic values are |
796 of single transitions for each symbol \<open>(, a, +, b, ), \<cdot>, c\<close>. |
755 facts or goals, and the operations are inferences. |
797 In Isar the algebraic values are facts or goals, and the operations |
756 |
798 are inferences. |
757 \<^medskip> |
799 |
758 The Isar/VM state maintains a stack of nodes, each node contains the local |
800 \<^medskip> |
759 proof context, the linguistic mode, and a pending goal (optional). The mode |
801 The Isar/VM state maintains a stack of nodes, each node |
760 determines the type of transition that may be performed next, it essentially |
802 contains the local proof context, the linguistic mode, and a pending |
761 alternates between forward and backward reasoning, with an intermediate |
803 goal (optional). The mode determines the type of transition that |
762 stage for chained facts (see \figref{fig:isar-vm}). |
804 may be performed next, it essentially alternates between forward and |
|
805 backward reasoning, with an intermediate stage for chained facts |
|
806 (see \figref{fig:isar-vm}). |
|
807 |
763 |
808 \begin{figure}[htb] |
764 \begin{figure}[htb] |
809 \begin{center} |
765 \begin{center} |
810 \includegraphics[width=0.8\textwidth]{isar-vm} |
766 \includegraphics[width=0.8\textwidth]{isar-vm} |
811 \end{center} |
767 \end{center} |
812 \caption{Isar/VM modes}\label{fig:isar-vm} |
768 \caption{Isar/VM modes}\label{fig:isar-vm} |
813 \end{figure} |
769 \end{figure} |
814 |
770 |
815 For example, in \<open>state\<close> mode Isar acts like a mathematical |
771 For example, in \<open>state\<close> mode Isar acts like a mathematical scratch-pad, |
816 scratch-pad, accepting declarations like @{command fix}, @{command |
772 accepting declarations like @{command fix}, @{command assume}, and claims |
817 assume}, and claims like @{command have}, @{command show}. A goal |
773 like @{command have}, @{command show}. A goal statement changes the mode to |
818 statement changes the mode to \<open>prove\<close>, which means that we |
774 \<open>prove\<close>, which means that we may now refine the problem via @{command |
819 may now refine the problem via @{command unfolding} or @{command |
775 unfolding} or @{command proof}. Then we are again in \<open>state\<close> mode of a proof |
820 proof}. Then we are again in \<open>state\<close> mode of a proof body, |
776 body, which may issue @{command show} statements to solve pending sub-goals. |
821 which may issue @{command show} statements to solve pending |
777 A concluding @{command qed} will return to the original \<open>state\<close> mode one |
822 sub-goals. A concluding @{command qed} will return to the original |
778 level upwards. The subsequent Isar/VM trace indicates block structure, |
823 \<open>state\<close> mode one level upwards. The subsequent Isar/VM |
779 linguistic mode, goal state, and inferences: |
824 trace indicates block structure, linguistic mode, goal state, and |
|
825 inferences: |
|
826 \<close> |
780 \<close> |
827 |
781 |
828 text_raw \<open>\begingroup\footnotesize\<close> |
782 text_raw \<open>\begingroup\footnotesize\<close> |
829 (*<*)notepad begin |
783 (*<*)notepad begin |
830 (*>*) |
784 (*>*) |
935 |
888 |
936 text_raw \<open>\end{minipage}\<close> |
889 text_raw \<open>\end{minipage}\<close> |
937 |
890 |
938 text \<open> |
891 text \<open> |
939 \<^medskip> |
892 \<^medskip> |
940 Such ``peephole optimizations'' of Isar texts are |
893 Such ``peephole optimizations'' of Isar texts are practically important to |
941 practically important to improve readability, by rearranging |
894 improve readability, by rearranging contexts elements according to the |
942 contexts elements according to the natural flow of reasoning in the |
895 natural flow of reasoning in the body, while still observing the overall |
943 body, while still observing the overall scoping rules. |
896 scoping rules. |
944 |
897 |
945 \<^medskip> |
898 \<^medskip> |
946 This illustrates the basic idea of structured proof |
899 This illustrates the basic idea of structured proof processing in Isar. The |
947 processing in Isar. The main mechanisms are based on natural |
900 main mechanisms are based on natural deduction rule composition within the |
948 deduction rule composition within the Pure framework. In |
901 Pure framework. In particular, there are no direct operations on goal states |
949 particular, there are no direct operations on goal states within the |
902 within the proof body. Moreover, there is no hidden automated reasoning |
950 proof body. Moreover, there is no hidden automated reasoning |
|
951 involved, just plain unification. |
903 involved, just plain unification. |
952 \<close> |
904 \<close> |
953 |
905 |
954 |
906 |
955 subsection \<open>Calculational reasoning \label{sec:framework-calc}\<close> |
907 subsection \<open>Calculational reasoning \label{sec:framework-calc}\<close> |
956 |
908 |
957 text \<open> |
909 text \<open> |
958 The existing Isar infrastructure is sufficiently flexible to support |
910 The existing Isar infrastructure is sufficiently flexible to support |
959 calculational reasoning (chains of transitivity steps) as derived |
911 calculational reasoning (chains of transitivity steps) as derived concept. |
960 concept. The generic proof elements introduced below depend on |
912 The generic proof elements introduced below depend on rules declared as |
961 rules declared as @{attribute trans} in the context. It is left to |
913 @{attribute trans} in the context. It is left to the object-logic to provide |
962 the object-logic to provide a suitable rule collection for mixed |
914 a suitable rule collection for mixed relations of \<open>=\<close>, \<open><\<close>, \<open>\<le>\<close>, \<open>\<subset>\<close>, \<open>\<subseteq>\<close> |
963 relations of \<open>=\<close>, \<open><\<close>, \<open>\<le>\<close>, \<open>\<subset>\<close>, |
915 etc. Due to the flexibility of rule composition |
964 \<open>\<subseteq>\<close> etc. Due to the flexibility of rule composition |
916 (\secref{sec:framework-resolution}), substitution of equals by equals is |
965 (\secref{sec:framework-resolution}), substitution of equals by |
917 covered as well, even substitution of inequalities involving monotonicity |
966 equals is covered as well, even substitution of inequalities |
918 conditions; see also @{cite \<open>\S6\<close> "Wenzel-PhD"} and @{cite |
967 involving monotonicity conditions; see also @{cite \<open>\S6\<close> "Wenzel-PhD"} |
919 "Bauer-Wenzel:2001"}. |
968 and @{cite "Bauer-Wenzel:2001"}. |
920 |
969 |
921 The generic calculational mechanism is based on the observation that rules |
970 The generic calculational mechanism is based on the observation that |
922 such as \<open>trans:\<close>~@{prop "x = y \<Longrightarrow> y = z \<Longrightarrow> x = z"} proceed from the premises |
971 rules such as \<open>trans:\<close>~@{prop "x = y \<Longrightarrow> y = z \<Longrightarrow> x = z"} |
923 towards the conclusion in a deterministic fashion. Thus we may reason in |
972 proceed from the premises towards the conclusion in a deterministic |
924 forward mode, feeding intermediate results into rules selected from the |
973 fashion. Thus we may reason in forward mode, feeding intermediate |
925 context. The course of reasoning is organized by maintaining a secondary |
974 results into rules selected from the context. The course of |
926 fact called ``@{fact calculation}'', apart from the primary ``@{fact this}'' |
975 reasoning is organized by maintaining a secondary fact called |
927 already provided by the Isar primitives. In the definitions below, |
976 ``@{fact calculation}'', apart from the primary ``@{fact this}'' |
|
977 already provided by the Isar primitives. In the definitions below, |
|
978 @{attribute OF} refers to @{inference resolution} |
928 @{attribute OF} refers to @{inference resolution} |
979 (\secref{sec:framework-resolution}) with multiple rule arguments, |
929 (\secref{sec:framework-resolution}) with multiple rule arguments, and |
980 and \<open>trans\<close> represents to a suitable rule from the context: |
930 \<open>trans\<close> represents to a suitable rule from the context: |
981 |
931 |
982 \begin{matharray}{rcl} |
932 \begin{matharray}{rcl} |
983 @{command "also"}\<open>\<^sub>0\<close> & \equiv & @{command "note"}~\<open>calculation = this\<close> \\ |
933 @{command "also"}\<open>\<^sub>0\<close> & \equiv & @{command "note"}~\<open>calculation = this\<close> \\ |
984 @{command "also"}\<open>\<^sub>n\<^sub>+\<^sub>1\<close> & \equiv & @{command "note"}~\<open>calculation = trans [OF calculation this]\<close> \\[0.5ex] |
934 @{command "also"}\<open>\<^sub>n\<^sub>+\<^sub>1\<close> & \equiv & @{command "note"}~\<open>calculation = trans [OF calculation this]\<close> \\[0.5ex] |
985 @{command "finally"} & \equiv & @{command "also"}~@{command "from"}~\<open>calculation\<close> \\ |
935 @{command "finally"} & \equiv & @{command "also"}~@{command "from"}~\<open>calculation\<close> \\ |
986 \end{matharray} |
936 \end{matharray} |
987 |
937 |
988 The start of a calculation is determined implicitly in the |
938 The start of a calculation is determined implicitly in the text: here |
989 text: here @{command also} sets @{fact calculation} to the current |
939 @{command also} sets @{fact calculation} to the current result; any |
990 result; any subsequent occurrence will update @{fact calculation} by |
940 subsequent occurrence will update @{fact calculation} by combination with |
991 combination with the next result and a transitivity rule. The |
941 the next result and a transitivity rule. The calculational sequence is |
992 calculational sequence is concluded via @{command finally}, where |
942 concluded via @{command finally}, where the final result is exposed for use |
993 the final result is exposed for use in a concluding claim. |
943 in a concluding claim. |
994 |
944 |
995 Here is a canonical proof pattern, using @{command have} to |
945 Here is a canonical proof pattern, using @{command have} to establish the |
996 establish the intermediate results: |
946 intermediate results: |
997 \<close> |
947 \<close> |
998 |
948 |
999 (*<*) |
949 (*<*) |
1000 notepad |
950 notepad |
1001 begin |
951 begin |